문제 : https://www.acmicpc.net/problem/17144
해당 문제 역시 시뮬레이션 문제였다.
공기청정기의 조건들과 그 외 문제들의 조건들 덕에 조금 헤매긴 했지만 하드코딩으로 문제를 해결하였다.
해결은 먼지 확산과 공기청정기 작동 두 가지 함수로 나눠서 접근하였다.
기본적으로 공기청정기는 위 방향과 아래 방향으로 주어진다는 사실과 차례대로 하드코딩하니 문제는 풀 수 있었지만 다소 아쉬움이 남는 풀이여서 다른 사람들의 풀이를 조금 찾아봤더니 공기청정기의 과정을 축소할 수 있을 것 같다.
방향에 따라 하나씩 나누는 방식이 아닌 예외 케이스만 잘 고려한다면 하나의 반복문으로 충분히 처리가능 할 듯하다.
다만 실제 시험에서는 바로 바로 생각이 날 수 있을지 모르겠다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n, m, t;
int mp[50][50];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
// 위치, 방향(even idx = 반시계, odd idx = 시계)
vector<pair<int,int>> cl;
// 확산
void scatter() {
// copy
int mpc[50][50];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
mpc[i][j] = 0; // 1 초 후 변해야할 값
// 확산
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 값이 있으면
if (mp[i][j] > 0) {
int dcnt = 0, x, y;
int val = mp[i][j] / 5;
// 4방 변화 값(0~3)
for (int k = 0; k < 4; k++) {
x = i + dx[k], y = j + dy[k];
if (x >= 0 && x < n && y >= 0 && y < m && mp[x][y] != -1) {
mpc[x][y] += val; // 더하기
dcnt++;
}
}
// 빼진 값 빼기
mpc[i][j] -= (val * dcnt);
}
}
}
// 확산변화값 처리
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 청정기는 넘어간다
if (mp[i][j] == -1)
continue;
mp[i][j] += mpc[i][j]; // 변화 값 처리
}
}
}
// 청정
void clean() {
// 청정기 개수 동장
for (int idx = 0; idx < cl.size(); idx++) {
int c = 1; // 회전방향
if (idx % 2 == 0)
c *= -1;
// 청정기 위치
int x = cl[idx].first, y = cl[idx].second;
// 시계 방향
if (c == 1) {
// 2 1 0 3
int d = 3;
int nx = x, ny = y;
for (int k = 0; k < 4; k++) {
if (d == 0)
d = 3;
else
d = (d - 1) % 4; // 시계
// 남 2
if (d == 2) {
nx = x + dx[d], ny = y + dy[d]; // 탐색 위치
while ( nx != n - 1) {
int nx2 = nx + dx[d], ny2 = ny + dy[d]; // 다음 위치
mp[nx][ny] = mp[nx2][ny2]; // 흡수
nx = nx + dx[d], ny = ny + dy[d]; // 이동
}
}
// 동 1
else if (d == 1) {
while (ny >= 0 && ny < m - 1) {
int nx2 = nx + dx[d], ny2 = ny + dy[d]; // 다음 위치
mp[nx][ny] = mp[nx2][ny2]; // 흡수
nx = nx + dx[d], ny = ny + dy[d]; // 이동
}
}
// 북 0
else if(d == 0) {
// 청소기 위치보다 위로가지 않게
while (nx != x) {
int nx2 = nx + dx[d], ny2 = ny + dy[d]; // 다음 위치
mp[nx][ny] = mp[nx2][ny2]; // 흡수
nx = nx + dx[d], ny = ny + dy[d]; // 이동
}
}
// 서 3
else if (d == 3) {
while (ny!=1) {
int nx2 = nx + dx[d], ny2 = ny + dy[d]; // 다음 위치
mp[nx][ny] = mp[nx2][ny2]; // 흡수
nx = nx + dx[d], ny = ny + dy[d]; // 이동
}
mp[nx][ny] = 0;
}
}
}
// 반시계 방향
else if (c == -1) {
// 0 1 2 3
int d = 3;
int nx = x, ny = y;
for (int k = 0; k < 4; k++) {
d = (d + 1) % 4; // 시계
// 북 0
if (d == 0) {
nx = x + dx[d], ny = y + dy[d]; // 탐색 위치
while (nx != 0) {
int nx2 = nx + dx[d], ny2 = ny + dy[d]; // 다음 위치
mp[nx][ny] = mp[nx2][ny2]; // 흡수
nx = nx + dx[d], ny = ny + dy[d]; // 이동
}
}
// 동 1
else if (d == 1) {
while (ny != m - 1) {
int nx2 = nx + dx[d], ny2 = ny + dy[d]; // 다음 위치
mp[nx][ny] = mp[nx2][ny2]; // 흡수
nx = nx + dx[d], ny = ny + dy[d]; // 이동
}
}
// 남 2
else if (d == 2) {
// 청소기 위치보다 위로가지 않게
while (nx != x) {
int nx2 = nx + dx[d], ny2 = ny + dy[d]; // 다음 위치
mp[nx][ny] = mp[nx2][ny2]; // 흡수
nx = nx + dx[d], ny = ny + dy[d]; // 이동
}
}
// 서 3
else if (d == 3) {
while (ny != 1) {
int nx2 = nx + dx[d], ny2 = ny + dy[d]; // 다음 위치
mp[nx][ny] = mp[nx2][ny2]; // 흡수
nx = nx + dx[d], ny = ny + dy[d]; // 이동
}
mp[nx][ny] = 0;
}
}
}
}
}
int main() {
cin >> n >> m >> t;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> mp[i][j];
if (mp[i][j] == -1) {
pair<int, int> p(i, j);
cl.push_back(p);
}
}
}
// t초후
for (int i = 0; i < t; i++) {
scatter();
clean();
}
// 정답
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (mp[i][j] > 0)
ans += mp[i][j];
cout << ans;
}
'Archived(CSE Programming) > 알고리즘(C++)' 카테고리의 다른 글
프로그래머스_N으로 표현 (0) | 2019.11.16 |
---|---|
프로그래머스_2*n 타일링 (0) | 2019.11.16 |
백준 14502_연구소 (0) | 2019.10.19 |
백준 15683_감시 (0) | 2019.10.17 |
백준 14890_경사로 (0) | 2019.10.16 |