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

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

17144번: 미세먼지 안녕!

 

약간의 bfs와 시뮬레이션이 혼합된 문제이다.

 

입력을 받은 이후에, 먼지가 있는 곳을 미리 큐에 넣어준다. 동시에 확산되어야 한다는 조건이 있기 때문이다.

 

미리 큐에 넣어주고, 한 번 탐색을 했을 때 큐의 크기만큼만 확산을 진행하면 단위 시간이 흘렀다고 볼 수 있다.

 

그리고, 이전에 발생했던 먼지의 확산이, 앞으로 발생하게 될 먼지의 확산에 영향을 끼치지 않게 하기 위해서

 

변화량을 따로 저장한 이후에, 확산을 마치고 변화량을 모두 구한 이후에 한꺼번에 반영해줘야 한다.

 

그렇지 않으면 동시에 확산했다는 조건을 만족시킬 수 없기 때문이다.

 

 

다음으로 환기에 대한 조건을 구현할 때는, 조건에 맞게 인덱스를 가지고 놀아주면 된다.

 

한 가지 주의할 사항은, 환기의 순서를 신경 써야 한다는 것이다.

 

먼저 빨려들어가서 없어지는 먼지의 값을 덮어 씌워주는 방향으로 순서를 정해야, 중간에 다른 구석 지점에서 먼지의 값이 누락되는 것을 방지할 수 있다.

 

따라서 먼저 빨려들어가는 쪽에 대한 처리를 먼저 해주는 방식으로 구현한다.

 

#include<iostream>
#include<queue>
using namespace std;
int m[52][52], T, R, C, dif[52][52];
bool vis[52][52];
pair<int, int> Up;
pair<int, int> Dn;
queue<pair<int, int> > q;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void clean() {
	//상부
	for (int i = 1; i <= Up.first - 1; i++)  //하향
		m[Up.first - i][0] = m[Up.first - 1 - i][0];
	for (int i = 0; i <= C - 2; i++) //좌향
		m[0][i] = m[0][i + 1];
	for (int i = 0; i <= Up.first - 1; i++) //상향
		m[i][C - 1] = m[i + 1][C - 1];
	for (int i = C - 1; i >= 1; i--) //우향
		m[Up.first][i] = m[Up.first][i - 1];


	//하부
	for (int i = Dn.first + 1; i <= R - 2; i++) //상향
		m[i][0] = m[i + 1][0];
	for (int i = 1; i <= C - 1; i++) //좌향
		m[R - 1][i - 1] = m[R - 1][i];
	for (int i = R - 1; i >= Dn.first + 1; i--)//하향
		m[i][C - 1] = m[i - 1][C - 1];

	for (int i = C - 1; i >= 1; i--) //우향
		m[Dn.first][i] = m[Dn.first][i - 1];
}

void bfs() {
	int cnt = q.size();
	while (cnt--) {
		pair<int, int> cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];
			if (nr < 0 || nc < 0 || nr >= R || nc >= C ) continue;
			if (nr == Up.first && nc == Up.second) continue;
			if (nr == Dn.first && nc == Dn.second) continue;
			
			dif[cur.first][cur.second] -= m[cur.first][cur.second] / 5;
			dif[nr][nc] += m[cur.first][cur.second] / 5;
		}
	}
	//update
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			m[i][j] += dif[i][j];
		}
	}
	//Print();
	clean();
}
void init() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			vis[i][j] = false;
			dif[i][j] = 0;
		}
	}
}
int main(void) {
	cin >> R >> C >> T;
	bool fst = true;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> m[i][j];
			if (m[i][j] == -1) {
				m[i][j] = 0;
				if (fst) {
					Up.first = i;
					Up.second = j;
					fst = false;
				}
				else {
					Dn.first = i;
					Dn.second = j;
				}
			}
		}
	}
	
	//1초 루틴
	while (T--) {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (m[i][j] != 0 && !vis[i][j]) { //방문 조건도 사실 필요없음
					q.push({ i, j });
					vis[i][j] = true;
				}
			}
		}
		bfs();
		init();
	}
	int Sum = 0;
	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++)
			Sum += m[i][j];
	cout << Sum << '\n';
	return 0;
}