[C++] BOJ(백준) 17144 미세먼지 안녕!

https://www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

 

구현, 시뮬레이션 문제다.

 

문제 설명

 

공기청정기가 존재한다. 공기 청정기는 2x1 크기로 항상 1열에 존재하고, 위 아래 행과 두 칸 이상 떨어져 있다.

 

각 칸에는 미세먼지가 존재하고 이는 해당 칸의 미세먼지 / 5 만큼 4방향으로 퍼진다.

해당 칸에는 퍼진 미세먼지를 제외한 양만큼 남는다. 

공기청정기가 존재하거나, 칸이 없는 경우는 퍼지지 않는다.

 

후에 공기 청정기가 작동하면 공기청정기 중간 지점을 기준으로 위는 반시계, 아래는 시계방향으로 순환한다.

공기청정기에 들어간 미세먼지는 정화되어 사라진다.

 

위 과정은 1초동안 일어나고, T초가 지난 후에 남은 미세먼지의 총 양을 구하는 문제다.

 

---

 

풀이

미세먼지 퍼짐을 구현할 때 주의해야 하는 부분은 모든 미세먼지의 퍼짐은 동시에 일어난다는 점이다.

배열을 순차적으로 순회하면서 그 때 그 때 배열의 값을 갱신하면 현재 미세 먼지의 양으로 계산되지 않는 칸이 발생한다.

따라서 새로운 배열을 만들고 거기에 변화치를 저장한 후, 변화치를 한 번에 갱신하는 방법을 이용했다.

 

여기서 실수했던 부분은 변화치를 저장하는 배열을 매번 초기화하지 않아 값이 엄청나게 증가했다.

ㅋㅋ

 

공기 청정기가 작동하는 부분을 구현하기 위해서는 특별한 방법이 떠오르지 않아 한 줄 씩 4번, 두 구역 각각 옮겼다.

 

---

 

최종코드

 

#include <iostream>
using namespace std;

int n, m, t, dir;
int arr[50][50];
int temp[50][50];
int gr = -1, gc = -1;

int dr[4] = { 0, 1, 0, -1 };
int dc[4] = { 1, 0, -1, 0 };



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> m >> t;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == -1)
				gr = i;
		}

	while (t--) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] > 0) {
					int tmp = arr[i][j] / 5;

					for (int k = 0; k < 4; k++) {
						int r = i + dr[k];
						int c = j + dc[k];

						if (r < 0 || c < 0 || r >= n || c >= m) continue;
						if (arr[r][c] == -1) continue;

						temp[r][c] += tmp;
						temp[i][j] -= tmp;
					}
				}
			}
		}

		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				arr[i][j] += temp[i][j];

		for (int i = gr + 2; i < n; i++) 
			arr[i - 1][0] = arr[i][0];

		for (int i = 1; i < m; i++) 
			arr[n - 1][i - 1] = arr[n - 1][i];

		for (int i = n - 1; i > gr; i--)
			arr[i][m - 1] = arr[i - 1][m - 1];

		for (int i = m - 1; i > 1; i--)
			arr[gr][i] = arr[gr][i - 1];



		for (int i = gr - 2; i > 0; i--)
			arr[i][0] = arr[i - 1][0];

		for (int i = 1; i < m; i++)
			arr[0][i - 1] = arr[0][i];

		for (int i = 0; i < gr - 1; i++)
			arr[i][m - 1] = arr[i + 1][m - 1];

		for (int i = m - 1; i > 1; i--)
			arr[gr - 1][i] = arr[gr - 1][i - 1];

		arr[gr][1] = 0;
		arr[gr - 1][1] = 0;

		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				temp[i][j] = 0;
	}

	int res = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			res += arr[i][j];

	cout << res + 2;

}