백준 17144번 미세먼지 안녕! (BFS)

백준 17144번 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

 

전형적인 맵 형태의 BFS 문제이다.

 

코드를 구현한 순서는 (bfs -> 위측 공기청정기 순환 -> 아래측 공기청정기 순환)을 t만큼 반복하는 것이다.

다만, 기존에 풀었던 문제와 달리 주의할 점은 미세먼지가 한번 확산할 때마다 미세먼지 값이 갱신되므로 q도 새롭게 갱신해줘야 한다.

따라서 bfs를 호출할 때, q에 새롭게 값을 입력해주는 것을 볼 수 있다.

 

그리고 map 값만 이용하면 미세먼지 값이 확산되면서 기존의 값이 변경되기 때문에, tempMap 변수를 이용해서 기존의 q에 넣었던 값을 그대로 사용해야 한다는 점도 주의해야 한다.

 

 

circulate 함수에서는 ccw와 cw 배열를 이용해서 위측과 아래측의 공기순환 방향을 지정했다.

예를들어 위측의 공기순환 방향은 우, 상, 좌, 하 형식으므로 ccw 에서 2, 1, 3, 0 값을 순서대로 dx, dy에 입력하면 우, 상, 좌, 하 형식으로 이동하게 된다.

아래측 순환은 2, 0, 3, 1 값을 순서대로 넣으면 우, 하, 좌, 상 순서대로 이동한다.

 

#include<iostream>
#include<queue>

using namespace std;

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

int ccw[4] = { 2,1,3,0 };
int cw[4] = { 2,0,3,1 };

int r, c, t;
int map[51][51];
int tempMap[51][51];

queue<pair<int, int>> q;

void bfs() {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (map[i][j] > 0) {
				q.push(make_pair(i, j));
			}
		}
	}

	while (!q.empty()) {
		int cx = q.front().first;
		int cy = q.front().second;
		q.pop();

		int dust = map[cx][cy] / 5;

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

			if (nx < 0 || ny < 0 || nx >= r || ny >= c) {
				continue;
			}

			if (map[nx][ny] != -1) {
				tempMap[nx][ny] += dust;
				tempMap[cx][cy] -= dust;
			}
		}
	}

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			map[i][j] = tempMap[i][j];
		}
	}
}

void circulate(int startX, int startY, int dir[]) {
	int cx = startX;
	int cy = startY + 1;

	for (int i = 0; i < 4; i++) {
		while (true) {
			int nx = cx + dx[dir[i]];
			int ny = cy + dy[dir[i]];

			if (nx == startX && ny == startY) break;

			if (nx < 0 || ny < 0 || nx >= r || ny >= c) break;

			tempMap[nx][ny] = map[cx][cy];
			cx = nx;
			cy = ny;
		}
	}

	tempMap[startX][startY+1] = 0;

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			map[i][j] = tempMap[i][j];
		}
	}
}

int main(void) {	
	cin >> r >> c >> t;

	int cleanerX = 0, cleanerY = 0;

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> map[i][j];
			tempMap[i][j] = map[i][j];

			if (map[i][j] == -1) {
				cleanerX = i, cleanerY = j;
			}
		}
	}

	for (int k = 0; k < t; k++) {

		bfs();
		circulate(cleanerX - 1 , cleanerY, ccw);
		circulate(cleanerX, cleanerY, cw);
	}

	int ans = 0;

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (map[i][j] != -1) {
				ans += map[i][j];
			}			
		}
	}
	
	cout << ans << '\n';

	return 0;
}