[Algorithm][C++] BOJ 17144 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

---

풀이 핵심

1. 공기청정기 행 (row) 위치 robot_r 배열에 저장

2. map 탐색 하며 미세먼지 큐에 저장 (위치 정보 r, c 와 미세먼지 양 map[r][c]를 저장)

   (처음에는 위치 정보만 저장했으나 미세먼지 확산이 동시에 일어난다고 생각해야 하므로 미세먼지 양도 저장해야 함)

3. bfs와 비슷하게 (추가 push가 없음) 확산 진행

4. 공기청정기의 위, 아래 순환 구현 (OverBound 만 조심)

5. 2, 3, 4 T번 진행

6. 남은 미세먼지 계산

 

---

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <queue>
using namespace std;

int R, C, T;
int map[1000][1000];
int robot_r[2]; //공기청정기의 행(row) 위치

struct pos {
	int r, c, dust;
};
queue<pos> q;

void InputData() {
	bool flag = false;
	scanf("%d %d %d", &R, &C, &T);
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j]) {
				if (map[i][j] == -1) {
					if (flag) robot_r[1] = i;
					else {
						robot_r[0] = i;
						flag = true;
					}
				}
			}
		}
	}
}

// 미세먼지 확산
void diffusion() {
	const int dr[] = { 1,-1,0,0 };
	const int dc[] = { 0,0,1,-1 };
	while (!q.empty()) {
		pos cur = q.front();
		q.pop();
		if (cur.dust < 5) continue; // 미세먼지 양이 5보다 작으면 확산 x
		int cnt = 0; // 확산 수 세기
		for (int dir = 0; dir < 4; dir++) {
			int nr = cur.r + dr[dir];
			int nc = cur.c + dc[dir];
			if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
			if (map[nr][nc] == -1) continue;
			cnt++;
			// map[cur.r][cur.c] / 5 로 하면 안된다
			// (확산은 동시에 일어나므로)
			map[nr][nc] += cur.dust / 5;
		}
		map[cur.r][cur.c] -= (cnt * (cur.dust / 5));
	}
}

void circulation() {
	// 공기청정기 위로 순환
	for (int i = robot_r[0] - 1; i >= 1; i--) {
		map[i][0] = map[i - 1][0];
	}
	for (int i = 0; i <= C - 2; i++) {
		map[0][i] = map[0][i + 1];
	}
	for (int i = 0; i <= robot_r[0] - 1; i++) {
		map[i][C - 1] = map[i + 1][C - 1];
	}
	for (int i = C - 1; i >= 2; i--) {
		map[robot_r[0]][i] = map[robot_r[0]][i - 1];
	}
	map[robot_r[0]][1] = 0;

	// 공기청정기 아래로 순환
	for (int i = robot_r[1] + 1; i <= R - 2; i++) {
		map[i][0] = map[i + 1][0];
	}
	for (int i = 0; i <= C - 2; i++) {
		map[R - 1][i] = map[R - 1][i + 1];
	}
	for (int i = R - 1; i >= robot_r[1] + 1; i--) {
		map[i][C - 1] = map[i - 1][C - 1];
	}
	for (int i = C - 1; i >= 2; i--) {
		map[robot_r[1]][i] = map[robot_r[1]][i - 1];
	}
	map[robot_r[1]][1] = 0;
}

void Solve() {
	while (T--) {
		// 미세먼지 q에 모두 담아준다
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (map[i][j] && map[i][j] != -1) {
					q.push({ i, j, map[i][j] });
				}
			}
		}
		diffusion();
		circulation();
	}
	// 미세먼지 수 계산
	int cnt = 0;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (map[i][j] && map[i][j] != -1) cnt += map[i][j];
		}
	}
	// 정답 출력
	printf("%d", cnt);
}

int main() {
	InputData();
	Solve();
	return 0;
}

---

아쉬운 점

1. 까다롭지 않은 시뮬레이션 문제라고 생각함

2. 하지만 미세먼지가 순환하는 것을 구현할 때 조금 더 효율적으로 반복문을 만들 수 있지 않았을 까