[백준 3197] 백조의 호수

문제 링크 : 3197번: 백조의 호수 (acmicpc.net)

3197번: 백조의 호수

문제

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

아래에는 세 가지 예가 있다.

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      처음               첫째 날             둘째 날

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

출력

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

---

Disjoint Set 을 이용한 문제이다.

특별하게도 이 문제는 일반적으로 알고있는 1차원 배열(parent[x])을 활용한 Distjoint Set 이 아니다.

2차원 배열(parent[x][y])을 활용해서 문제를 해결해야 하는데 원리 자체는 동일하기 때문에 크게 어렵지는 않았던거 같다.

 

문제 접근 방법

1. 2차원 배열 parent에 대한 초기화 작업을 해준다.

이때 parent[x][y] 를 하나의 특정값으로 나타내려고 한다.

즉, (x, y) 좌표를 하나의 특정값으로 변환하고 해당 값을 다시 (x, y) 으로 변환할 수 있도록 해주는 함수를 만들어줘야 한다.

 

♣ (x, y) 를 하나의 특정값으로 변환하는 함수는 다음과 같다.

int get_2_to_1(int x, int y) {
	return (x - 1) * C + y;
}

 

♣ 하나의 특정값을 원래의 (x, y) 값으로 변환하는 함수는 다음과 같다.

pair<int, int> get_1_to_2(int t) {
	pair<int, int> ret;
	ret.first = (t - 1) / C + 1;
	ret.second = (t % C == 0 ? C : t % C);
	return ret;
}

 

parent[x][y] = get_2_to_1(x, y) 를 통해 (1, 1) 부터 (R, C) 까지 모든 좌표들에 대한 disjoint set의 초기화 작업이 완료되었다.

 

2. 빙판과 호수에 대한 분리작업을 해줘야 한다.

여기서 주의해야 할 점은 오리(Map[x][y] = 'L')가 현재 물 위에 떠있다는 것을 유의해야 한다.

즉, Union 작업을 진행할 때, 오리의 위치(Map[x][y] = 'L')와 물의 위치(Map[x][y] = '.')를 동일하게 바라봐야 하는 것이 핵심이다. (질문 검색의 힌트를 통해 알아낸 점)

그리고 다음날에 녹아버릴 빙판의 위치를 담도록 하는 큐 Q라고 할 때, 다음과 같은 경우를 고려하여 Union 하거나 Q 에 담도록 해준다.

• 현재 위치가 빙판이 아닐 경우 다음 위치가 빙판인 경우 : Q에 다음 위치(nextX, nextY) 를 push 한다.
• 현재 위치가 빙판이 아닐 경우 다음 위치 또한 빙판이 아닐 경우 : 물의 공간이므로 두 위치에 존재하는 물들을 Union 해줘야 한다.

 

3. 첫번째 오리의 위치와 두번째 오리의 위치가 만나는지 확인한다.

• 두 오리가 만나는 경우 : 두 오리가 동일한 물 위에 존재한다.  (두 위치의 parent 값이 동일)
• 두 오리가 만나지 못할 경우 : 두 오리가 동일한 물 위에 존재하지 않는다. (두 위치의 parent 값이 동일 x) 

 

4. 두 오리가 만나지 못할 경우 다음날에 녹아버릴 빙판의 위치를 담은 큐 Q 를 pop 하여 해당 위치의 빙판을 물로 만들어 준다. (Map[x][y] = 'X' => '.')

그 후에 2번 작업에서와 동일하게 Union 작업 및 그 다음날에 녹아버릴 빙판의 위치를 다시 큐 Q에 담아주도록 한다.

그 후에 3번 작업으로 이동한다.

 

5. 두 오리가 만나게 된 경우 지나온 날 day 값을 출력한다.

 

Solution Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <math.h>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

bool is_meet(int x1, int y1, int x2, int y2);
void Union(int x1, int y1, int x2, int y2);

int R, C;
int L_x[2], L_y[2];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int parent[1502][1502];
char Map[1502][1502];
bool check[1502][1502];
queue<pair<int, int>> Q;

void input() {
	cin >> R >> C;
	for (int i = 1; i <= R; i++) {
		string S;
		cin >> S;
		for (int j = 1; j <= C; j++) {
			Map[i][j] = S[j - 1];
			if (Map[i][j] == 'L') {
				if (!L_x[0]) L_x[0] = i, L_y[0] = j;
				else L_x[1] = i, L_y[1] = j;
			}
		}
	}
}

int get_2_to_1(int x, int y) {
	return (x - 1) * C + y;
}

pair<int, int> get_1_to_2(int t) {
	pair<int, int> ret;
	ret.first = (t - 1) / C + 1;
	ret.second = (t % C == 0 ? C : t % C);
	return ret;
}


void init() {
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			parent[i][j] = get_2_to_1(i, j);
		}
	}
}

void map_separate() {
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (Map[i][j] != 'X') {
				for (int k = 0; k < 4; k++) {
					int nextX = i + dx[k], nextY = j + dy[k];
					if (nextX >= 1 && nextX <= R && nextY >= 1 && nextY <= C) {
						if (Map[nextX][nextY] == 'X' && !check[nextX][nextY]) {
							Q.push({ nextX, nextY });
							check[nextX][nextY] = true;
						}
						else if (Map[nextX][nextY] != 'X' && !is_meet(i, j, nextX, nextY)) {
							Union(i, j, nextX, nextY);
						}
					}
				}
			}
		}
	}
}

int get_parent(int x, int y) {
	if (parent[x][y] == get_2_to_1(x, y)) {
		return parent[x][y];
	}
	pair<int, int> p = get_1_to_2(parent[x][y]);
	return parent[x][y] = get_parent(p.first, p.second);
}

void Union(int x1, int y1, int x2, int y2) {
	int X = get_parent(x1, y1);
	int Y = get_parent(x2, y2);
	pair<int, int> p1 = get_1_to_2(X);
	pair<int, int> p2 = get_1_to_2(Y);
	if (X > Y) parent[p1.first][p1.second] = Y;
	else parent[p2.first][p2.second] = X;
}

bool is_meet(int x1, int y1, int x2, int y2) {
	if (get_parent(x1, y1) == get_parent(x2, y2))
		return true;
	return false;
}

void solution() {
	int day = 0;
	init();
	map_separate();
	while (!is_meet(L_x[0], L_y[0], L_x[1], L_y[1])) {
		queue<pair<int, int>> new_Q;
		while (!Q.empty()) {
			int x = Q.front().first, y = Q.front().second;
			Q.pop();

			check[x][y] = false, Map[x][y] = '.';
			for (int i = 0; i < 4; i++) {
				int nextX = x + dx[i], nextY = y + dy[i];
				if (nextX >= 1 && nextX <= R && nextY >= 1 && nextY <= C) {
					if (Map[nextX][nextY] == 'X' && !check[nextX][nextY]) {
						new_Q.push({ nextX, nextY });
						check[nextX][nextY] = true;
					}
					else if (Map[nextX][nextY] != 'X' && !is_meet(x, y, nextX, nextY)) {
						Union(x, y, nextX, nextY);
					}
				}
			}
		}
		Q = new_Q;
		day += 1;
	}
	cout << day;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	solution();
	
	return 0;
}