[BOJ17144] 미세먼지 안녕!

[BOJ17144] 미세먼지 안녕!

문제 링크

문제 설명

• 2019 상반기 DS 공채 및 네트워크사업부 인턴 코테문제였다.
• 단순 시뮬레이션 문제.
• 미세먼지가 보드판에 있고, 공기청정기가 놓여있는 칸이나 보드판 밖으로는 확산되지 않으며 네방향으로 퍼진다. 퍼지는 규칙은 문제 참고.
• 미세먼지가 한번 확산되고 나면, 공기청정기에 의해 공기가 순환된다.
• 1초동안 위의 두문장이 실행되고, 주어진 초동안 반복되어 마지막에 보드판에 남아있는 미세먼지의 총합을 구하는 문제이다.

코드 리뷰

• 어려운 알고리즘이나 내용이 있진 않고 단순 시뮬레이션 문제였다.
• 그 당시 시험볼 땐 긴장 + 공기청정기 순환에 있어 어렵게 접근하고 비쥬얼스튜디오와 삼성코테시험 컴파일러의 미묘한 문법 차이때문에 멘탈이 나가 풀지 못하였다.
• 먼저 미세먼지들은 동시에 확산된다고 했으므로 큐에 넣고 확산되는 부분들은 tmp배열에 저장, 확산되고 원래자리에 남아있는 부분들은 보드배열에서 차감시켜 놓고, 마지막에 tmp 배열에 있는 값들을 보드판에 더해준다.
• 순환은 시계방향으로 순환한다하면 반시계방향으로 접근하면 헷갈리지 않고 풀 수 있다. 반시계방향으로 순환한다하면 시계방향으로 접근해라!
• 문제 푸는데 걸린 시간 1시간 20분.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

typedef struct {
	int r;
	int c;
}location;

queue <location> dust;
int m1r, m1c, m2r, m2c;
int board[51][51];
int dr[4] = { 0,0,-1,1 };
int dc[4] = { -1,1,0,0 };
int tmpboard[51][51];
int R, C, T;

void dust_sp() {
	memset(tmpboard,0, sizeof(tmpboard));
	while (!dust.empty()) {
		int r = dust.front().r;
		int c = dust.front().c;
		dust.pop();
		int scnt = 0;
		for (int k = 0; k < 4; k++) {
			int rnext = r + dr[k];
			int cnext = c + dc[k];
			if (rnext < 0 || rnext >= R || cnext < 0 || cnext >= C || 
				(rnext == m1r && cnext == m2c) || (rnext == m2r && cnext == m2c))
				continue;
			tmpboard[rnext][cnext] += board[r][c] / 5;
			scnt++;
		}
		board[r][c] -= (board[r][c] / 5) * scnt;
	}
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			board[r][c] += tmpboard[r][c];
		}
	}
}

void cycle1() {
	int rstart = m1r;
	int cstart = m1c;
	for (int r = rstart - 1; r >= 0; r--) {
		if (r == rstart - 1) continue;
		board[r + 1][cstart] = board[r][cstart];
	}
	for (int c = cstart + 1; c < C; c++) {
		board[0][c - 1] = board[0][c];
	}
	for (int r = 1; r <= rstart; r++) {
		board[r - 1][C - 1] = board[r][C - 1];
	}
	for (int c = C - 2; c >= cstart; c--) {
		if (c == cstart) board[rstart][c + 1] = 0;
		else board[rstart][c + 1] = board[rstart][c];
	}
}

void cycle2() {
	int rstart = m2r;
	int cstart = m2c;
	for (int r = rstart + 1; r < R; r++) {
		if (r == rstart + 1) continue;
		board[r - 1][cstart] = board[r][cstart];
	}
	for (int c = cstart + 1; c < C; c++) {
		board[R - 1][c - 1] = board[R - 1][c];
	}
	for (int r = R - 2; r >= rstart; r--) {
		board[r + 1][C - 1] = board[r][C - 1];
	}
	for (int c = C - 2; c >= cstart; c--) {
		if (c == cstart) board[rstart][c + 1] = 0;
		else board[rstart][c + 1] = board[rstart][c];
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> R >> C >> T;
	
	int idx = 0;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> board[r][c];
			if (board[r][c] != 0 && board[r][c] != -1) {
				dust.push({ r,c });
			}
			if (board[r][c] == -1 && idx == 0) {
				m1r = r; m1c = c;
				idx++;
			}
			if (board[r][c] == -1 && idx == 1) {
				m2r = r; m2c = c;
			}
		}
	}
	while (T--) {
		dust_sp();
		cycle1();
		cycle2();
		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (board[r][c] != 0 && board[r][c] != -1) {
					dust.push({ r,c });
				}
			}
		}
	}
	int ans = 0;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c] == -1) continue;
			ans += board[r][c];
		}
	}
	cout << ans << '\n';
	return 0;
}