[BOJ] 1888 곰팡이

문제 요약

문제 링크: 백준 1888 - 곰팡이

문제 설명

---

접근 방법

곰팡이들이 번호에 관계없이 하나로 연결되어 있는지 BFS로 매 단위시간마다 검색할 수 있다.

만약 아직 하나로 연결되어있지 않다면, 곰팡이의 자라는 속도 K에 비례하여 범위만큼 전염시킨다. 주의해야할 점은 더 큰 K의 곰팡이가 작은 K의 지역을 덮어 씌워야 한다는 점이다. K를 기준으로 정렬한 수, K가 작은 순서부터 전염을 시켜주면 자동으로 덮어 씌우는 조건을 만족시켜줄 수 있다.

---

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, ans;
int d[8][2] = { {0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,-1},{-1,1} };
char mat[101][101];
int vis[101][101];
vector<tuple<int, int, int>>v;

void bfs(int y,int x) {
	queue<pair<int, int>>q;
	vis[y][x] = 1;
	q.push({ y,x });
	while (q.size()) {
		y = q.front().first;
		x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int yy = y + d[i][0];
			int xx = x + d[i][1];
			if (yy >= n || yy < 0 || xx >= m || xx < 0)
				continue;
			if (!vis[yy][xx] && mat[yy][xx] != '0') {
				q.push({ yy,xx });
				vis[yy][xx] = 1;
			}
		}
	}
}

void f() {   // 곰팡이의 전이, 전이속도 오름차순 기준으로 정렬 후 시뮬레이션
	sort(v.begin(), v.end());
	for (auto k : v) {
		int p = get<0>(k);
		int y = get<1>(k);
		int x = get<2>(k);
		for (int i = max(0, y - p); i <= min(n - 1, y + p); i++) {
			for (int j = max(0, x - p); j <= min(m - 1, x + p); j++) {
				mat[i][j] = p + '0';
			}
		}
	}
}

void init() {
	for (int i = 0; i < 101; i++) {
		for (int j = 0; j < 101; j++) vis[i][j] = 0;
	}
	v.clear();
}

void solve() {
	while (1) {
		init();
		bool chk = 0, go = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (mat[i][j] != '0' && !vis[i][j]) {
					if (chk) {  
						go = 1;  // 한 덩어리가 아님
						break;
					}
					bfs(i, j);
					chk = 1;
				}
			}
			if (go)
				break;
		}
		if (!go && chk) {
			cout << ans;
			return;
		}
		ans++;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (mat[i][j] != '0') {
					v.push_back({ mat[i][j] - '0',i,j });
				}
			}
		}
		f();
	}
}

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> mat[i];
}

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