[BOJ/Platinum 5] 백준 23634 미안하다 이거 보여주려고 어그로 끌었다(C++)

문제 링크

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

23634번: 미안하다 이거 보여주려고 어그로 끌었다

문제

난 나뭇잎 마을의 초대 호카게인 센쥬 하시라마의 동생, 센쥬 토비라마라고 한다. 지금 우리 마을은 크나큰 위기에 빠져있다. 우리와 끊이지 않는 악연을 지닌 우치하 가문의 수장 우치하 마다라가 구미를 끌고 마을을 습격했기 때문이지. 형은 호카게로서 마다라와 전투를 벌이고 있고 마을 주민들에게 피해가 갈까 봐 제대로 전투하지 못하고 있어. 지금 놈의 화둔이 마을로 넘어오지 못하게 우리 형의 목둔이 막아주고 있으니 나무가 크게 불타기 전에 미리 주민들을 대피시켜야 해. 나뭇잎 마을을 지키려면 네 도움이 필요해. 

현재 상황은 마을 뒷산에서 전투가 일어나고 있고, 형의 나무가 불길을 막아서고 있어. 지도를 통해 살펴보면 마을 뒷산은 N×M의 직사각형의 격자에 해당하는 형태임을 알 수 있지. 아, 지도의 밖은 돌로 둘러싸여 있어 불이 퍼질 수 없으니 걱정하지 마.

불은 상하좌우로 인접한 나무를 통해서만 퍼져나갈 수 있고, 어떤 날에서 그다음 날로 넘어갈 때, 각 불은 동시에 퍼지게 돼. 불과 접촉한 나무는 다음 날 전부 불에 타서 불길이 되어버려. 하지만, 돌이 있는 지역은 불이 붙지 않아. 

너도 알다시피 대피에는 시간이 굉장히 중요해. 우리는 주민들이 안전히 대피할 수 있도록 만날 수 있는 모든 불이 합쳐지는 최소 시간과 그때의 불의 크기를 구해야만 해. 불이 돌에 막혀 모든 불이 하나로 합쳐지지 않을 수도 있는데, 그럴 땐 합쳐질 수 있는 모든 불이 합쳐지는 최소 시간과 그때의 불의 크기의 합을 구하면 돼.

불이 합쳐진다는 것은 불이 다른 불과 상하좌우로 인접하게 되는 것을 뜻하고, 불의 크기는 불이 붙은 칸의 개수를 말해.

부탁해! 어서! 문제를 해결해서 우리 마을과 형에게 도움을 줘!

입력

첫 번째 줄에 지도의 크기를 나타내는 정수 N, M이 주어진다. (1≤N,M≤2,000)

두 번째 줄부터 N+1번째 줄까지 0,1,2로 이루어진 첫날 지도가 표시된다. (불 = 0, 나무 = 1, 돌 = 2)

출력

만날 수 있는 모든 불이 만나는 최소 시간과 그때의 불의 크기의 합을 출력한다. 첫날은 0일차이다. 즉, 처음부터 합칠 수 있는 모든 불이 합쳐져 있다면 최소 시간은 0이다.

만약 퍼질 불이 없다면, "0 0"을 출력한다.

예제 입력 1

5 11
00111110100
01111110111
01111111110
11110011111
11000000111

예제 출력 1

2 53

예제 입력 2

5 6
011112
201120
022211
111101
111111

예제 출력 2

2 20

예제 입력 3

3 3
111
101
111

예제 출력 3

0 1

알고리즘 분류

• 그래프 탐색
• 유니온 파인드

풀이

BFS와 유니온 파인드를 사용한다는 점에서 문명과 굉장히 유사한 문제였지만 본인은 이 문제가 더 어려웠다.

14868번: 문명

처음에는 한 칸에 있는 0을 한 개의 불로 보고 코드를 짰지만 실패했고, 따라서 처음 정보가 주어졌을 때 인접한 0들을 하나의 불로 보고 BFS를 통하여 불의 개수를 구했다. 또한, 돌로 막혀 불이 합쳐지지 않는 경우(예제 2) 때문에 BFS를 한번 더 써서 돌로 나눠진 구역의 개수를 구하였다. (알고리즘 고수인 아는 분에게 여쭤보았다.)

그리고 set을 사용하여, 유니온 파인드를 통해 구한 분리 집합의 개수와 구역의 개수가 다르면 계속 불을 확장시키고 합치며, 개수가 같다면 반복문을 종료하고 일 수(년 수인 줄 알고 Year로 함)와 불의 개수(격자의 0의 개수)를 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 2001
#define LL long long
#define INF 2e9

using namespace std;
int N, M;
int Fire = 1; // 불의 개수
int Region = 0; // 구역의 개수
int MAP[MAX][MAX]; // 격자
int Fire_Number[MAX][MAX]; // 현재 칸의 불의 번호(MAP[Y][X] == 0일 때)
bool visited[MAX][MAX]; // 구역을 나눌 때 쓰이는 방문 표시 배열
int Parent[MAX * MAX];
queue<pair<int, int> > Q;
queue<pair<int, int> > P;
int moveY[4] = { -1,0,1,0 };
int moveX[4] = { 0,-1,0,1 };
int Year = 0;

void init() {
	for (int i = 1; i <= Fire; i++) {
		Parent[i] = -1;
	}
}

int Find_Group(int X) {
	if (Parent[X] == -1) {
		return X;
	}
	return Parent[X] = Find_Group(Parent[X]);
}

void Union_Group(int X, int Y) {
	X = Find_Group(X);
	Y = Find_Group(Y);
	if (X != Y) {
		Parent[X] = Y;
	}
}

void Fire_Numbering(int Y, int X, int I) {
	queue<pair<int, int> > T;
	Fire_Number[Y][X] = I;
	T.push(make_pair(Y, X));
	Q.push(make_pair(Y, X));

	while (!T.empty()) {
		int CurY = T.front().first;
		int CurX = T.front().second;
		T.pop();

		for (int i = 0; i < 4; i++) {
			int nextY = CurY + moveY[i];
			int nextX = CurX + moveX[i];
			if ((nextY >= 0) && (nextY < N) && (nextX >= 0) && (nextX < M) && (MAP[nextY][nextX] == 0)) {
				if (Fire_Number[nextY][nextX] == 0) {
					Fire_Number[nextY][nextX] = I;
					T.push(make_pair(nextY, nextX));
					Q.push(make_pair(nextY, nextX));
				}
			}
		}
	};
}

void Region_Numbering(int Y, int X) {
	queue<pair<int, int> > T;
	visited[Y][X] = true;
	T.push(make_pair(Y, X));

	while (!T.empty()) {
		int CurY = T.front().first;
		int CurX = T.front().second;
		T.pop();

		for (int i = 0; i < 4; i++) {
			int nextY = CurY + moveY[i];
			int nextX = CurX + moveX[i];
			if ((nextY >= 0) && (nextY < N) && (nextX >= 0) && (nextX < M) && (MAP[nextY][nextX] != 2) && !visited[nextY][nextX]) {
				visited[nextY][nextX] = true;
				T.push(make_pair(nextY, nextX));
			}
		}
	};
}

bool Fire_Parent() {
	set<int> S;
	for (int i = 1; i <= Fire; i++) {
		S.insert(Find_Group(i));
	}
	if (S.size() == Region) {
		return true;
	}
	return false;
}

bool BFS() {
	while (!Q.empty()) {
		int CurY = Q.front().first;
		int CurX = Q.front().second;
		Q.pop();

		P.push(make_pair(CurY, CurX));

		for (int i = 0; i < 4; i++) {
			int nextY = CurY + moveY[i];
			int nextX = CurX + moveX[i];
			if ((nextY >= 0) && (nextY < N) && (nextX >= 0) && (nextX < M) &&
				(Fire_Number[nextY][nextX] > 0) && (Fire_Number[nextY][nextX] != Fire_Number[CurY][CurX])) {
				int CurF = Fire_Number[CurY][CurX];
				int nextF = Fire_Number[nextY][nextX];
				if (Find_Group(CurF) != Find_Group(nextF)) {
					Union_Group(CurF, nextF);
				}
			}
		}
	};

	if (Fire_Parent()) {
		return false;
	}

	while (!P.empty()) {
		int CurY = P.front().first;
		int CurX = P.front().second;
		P.pop();

		for (int i = 0; i < 4; i++) {
			int nextY = CurY + moveY[i];
			int nextX = CurX + moveX[i];
			if ((nextY >= 0) && (nextY < N) && (nextX >= 0) && (nextX < M) && (MAP[nextY][nextX] == 1) && (Fire_Number[nextY][nextX] == 0)) {
				Fire_Number[nextY][nextX] = Fire_Number[CurY][CurX];
				Q.push(make_pair(nextY, nextX));
			}
		}
	};

	return true;
}

int Fire_Count() {
	int res = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (Fire_Number[i][j] > 0) {
				res++;
			}
		}
	}
	return res;
}

int main() {
	FIRST
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string S;
		cin >> S;
		for (int j = 0; j < M; j++) {
			MAP[i][j] = (S[j] - '0');
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if ((MAP[i][j] == 0) && (Fire_Number[i][j] == 0)) {
				Fire_Numbering(i, j, Fire++);
			}
		}
	}
	Fire--;
	init();

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if ((MAP[i][j] == 0) && (!visited[i][j])) {
				Region_Numbering(i, j);
				Region++;
			}
		}
	}

	if (Fire == 0) {
		cout << 0 << " " << 0 << "\n";
	}
	else {
		while (1) {
			bool Flag = BFS();
			if (!Flag) {
				break;
			}
			Year++;
		};

		cout << Year << " " << Fire_Count() << "\n";
	}

	return 0;
}