취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1888번 문제인 곰팡이이다.
문제는 아래 링크를 확인하자.

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

어느 순간에 모든 곰팡이가 한 덩어리가 되는지를 구하는 문제이다.

매 초마다 (1) 현재 모든 곰팡이가 연결되어있는지를 bfs를 통해 확인하고 (2) 그렇지 않다면 1초 뒤의 곰팡이의 상태를 나타내는 판을 새로 만드는 것을 반복해 문제를 해결하자.

초기상태로부터 길어야 100일 이내에 곰팡이는 한 덩어리가 되고, 각 곰팡이에 대해 번져나갈 칸을 하나하나 조사하는 것은 많아야 1만개의 칸에서 주변 121개의 칸을 조사하는 것으로 가능하므로 무식한 구현으로도 2초의 제한시간 내에 충분히 통과할 수 있다.

아래는 제출한 소스코드이다.

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

int R, C, sR, sC;
char board[100][100];
char tmp[100][100];
int ans, cnt;
int visited[100][100];

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

queue<pair<int, int>> que;

int bfs() {
	int ret = 1;
	memset(visited, 0, sizeof(visited));

	que.push(make_pair(sR, sC));
	visited[sR][sC] = 1;
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
			if (board[rr][cc] && !visited[rr][cc]) {
				visited[rr][cc] = 1;
				que.push(make_pair(rr, cc));
				ret++;
			}
		}
	}

	return ret;
}

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

	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> board[r][c];
			if (board[r][c] > '0') {
				sR = r, sC = c;
				cnt++;
			}
			else board[r][c] = 0;
		}
	}

	if (!board[sR][sC]) {
		cout << 0;
		return 0;
	}

	while (bfs() < cnt) {
		ans++;
		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (board[r][c]) {
					int k = board[r][c] - '0';
					for (int rr = r - k; rr <= r + k; rr++) {
						for (int cc = c - k; cc <= c + k; cc++) {
							if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
							tmp[rr][cc] = max(tmp[rr][cc], board[r][c]);
						}
					}
				}
			}
		}
		swap(board, tmp);

		cnt = 0;
		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (board[r][c]) cnt++;
			}
		}
	}

	cout << ans;
}