백준 17144번 미세먼지여 안녕!(C++)

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

17144번: 미세먼지 안녕!

 

 시뮬레이션, 구현 문제이다. 굳이 따지자면 그래프 탐색까지 포함시킬 수 있겠다. 아무튼 탐색이니까.

문제 자체는 이해하기 쉽다.

미세먼지가 있는 칸은 사방으로 확산되고 공기청정기는 시계방향, 반시계 방향으로 순환한다.

중요한 포인트는

1. 미세먼지는 "동시에" 확산된다.

2. 공기청정기는 행렬의 외부만 회전한다.

 

동시 확산을 처리하는 것이 중요하다 왜냐하면 

 

0 5 0

0 10 0

0 0 0

 

이라고 할 때, 만약 그냥 순서대로 확산시키면 

1 2 1

0 11 0

0 0 0 

 

이 되어버린 후 확산하기 때문에 예상값을 벗어날 수 있다. 때문에 나의 경우는

1. 체크하여 만약 지금 확산시키려는 칸이 먼지가 있는 칸 일 경우는 확산 X

2. 다만 확산 카운트는 증가한다

3. 그리고 원래 확산했어야할 값을 임시 벡터에 보존해둔다.

4. 마지막에 확산됐어야할 값을 갱신한다. 

 

조금 메모리가 많이들고 시간이 낭비될 수 있다는 생각이 들지만 나에게는 최선이었고 다른 사람들도 방법의 차이는 있어도 로직은 같은 것 같다.

 

#include <iostream>
#include <vector>
#define MAX 51

using namespace std;

vector<pair<int, int>> dustzone;

int room[MAX][MAX];
bool check[MAX][MAX];
int temptroom[MAX][MAX];
int hi = -1;
int lo = -1;
int R, C, T;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

void expend(int x, int y) {
	int cnt = 0;

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx < R && nx > -1 && ny < C && ny > -1 && room[nx][ny] != -1) {
			if (check[nx][ny] == false)
				room[nx][ny] += room[x][y] / 5;
			else
				temptroom[nx][ny] += room[x][y] / 5;
			cnt++;
		}
	}

	room[x][y] -= (room[x][y] / 5) * cnt;
}

void cleaning(int hi, int lo) {
	for (int i = hi - 1; i > 0; i--) {
		room[i][0] = room[i - 1][0];
	}

	for (int i = 0; i < C - 1; i++) {
		room[0][i] = room[0][i + 1];
	}

	for (int i = 0; i < hi; i++) {
		room[i][C - 1] = room[i + 1][C - 1];
	}

	for (int i = C - 1; i > 0; i--) {
		room[hi][i] = room[hi][i - 1];
	}

	room[hi][1] = 0;
	
	for (int i = lo + 1; i < R; i++) {
		room[i][0] = room[i + 1][0];
	}

	for (int i = 0; i < C - 1; i++) {
		room[R - 1][i] = room[R - 1][i + 1];
	}

	for (int i = R - 1; i > lo; i--) {
		room[i][C - 1] = room[i - 1][C - 1];
	}

	for (int i = C - 1; i > 0; i--) {
		room[lo][i] = room[lo][i - 1];
	}

	room[lo][1] = 0;
}

void init() {
	dustzone.clear();
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (room[i][j] >= 5) {
				check[i][j] = true;
				dustzone.push_back({ i,j });
			}
			temptroom[i][j] = 0;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> R >> C >> T;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> room[i][j];
			if (room[i][j] == -1) {
				if (hi == -1)
					hi = i;
				else
					lo = i;
			}
		}
	}
	for (int t = 0; t < T; t++) {
		init();

		for (auto a : dustzone) {
			expend(a.first, a.second);
		}

		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (temptroom[i][j] != 0)
					room[i][j] += temptroom[i][j];
			}
		}
		cleaning(hi, lo);
		//cout << endl;
		/*for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				cout << room[i][j] << " ";
			}
			cout << endl;
		}*/
	}
	int answer = 0;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			answer += room[i][j];
		}
	}
	cout << answer + 2 << '\n';
}