[BOJ] 3197 : 백조의 호수

문제 링크

3197번: 백조의 호수 (acmicpc.net)

3197번: 백조의 호수

빙판에 막혀 서로 만날 수 없는 두 백조가 빙판이 녹아 만나기 위해선 며칠이 걸리는지 출력하는 문제.

'.'은 물, 'X'는 빙판 'L'은 백조를 나타낸다.

물과 인접한 빙판은 하루에 걸쳐 녹는다.

 

풀이

처음에 문제를 제대로 안 읽어서 두 백조가 최단거리로 만나기 위해 필요한 날을 출력하는 것인 줄 알았다. 그래서 한참을 헛고생하다가 알고리즘 분류가 다익스트라가 아닌 것을 보고 문제를 다시 읽었다 ㅠㅠ.

이 문제는 최단 거리가 아닌 두 백조가 서로 만날 수 있기만 하면 된다. Union-Find를 이용해서 두 백조가 같은 집합안에 있다면 두 백조는 만날 수 있는 것으로 생각한다

1. 입력받을 때, 입력이 L이면 백조이므로 그 위치를 L1, L2에 각각 저장한다.  또한 입력이 물( . )이면 큐에 그 좌표를 넣는다. 입력이 빙판( X )이면 따로 처리할 건 없다.

나는 water라는 큐를 만들어서 물의 좌표를 저장했다.

※ 주의해야할 점

처음 입력에 입력받을 때 백조가 있는 공간도 물이므로 백조가 있는 좌표도 water 큐에 집어 넣어준다.

 

2.  water에 저장된 좌표를 기반으로 BFS로 상하좌우를 탐색한다. 만약 인접한 부분이 물이면 물끼리는 이어져야하므로 Union을 통해 결합한다. 인접한 부분이 빙판이면 이 부분을 물로 만들고 Union을 통해 결합한다. 그리고 빙판에서 물로 바뀌었으므로 그 좌표는 water 큐에 새로운 값으로 넣는다.

 

3. 상하좌우 모두 Union 한 후 만약 L1(백조1) 과 L2(백조2)가 같은 집합에 있다면, 즉 Parent가 같다면 물길이 이어진 것이므로 그때까지 걸린 날을 출력한다.

 

내가 만난 반례

1 17
LXX.XXL

입력이 이렇게 주어졌을 때, 내가 생각한 알고리즘 대로라면 water 큐에는 L, . , L의 좌표가 들어가게 되고

1일차에 L....L 이 되므로 답은 1이다. 그런데 처음 내가 짠 코드는 1일차 후 {'L' , '.'}, {'.' , '.' , '.'}, {'.' , 'L'} 이렇게 세 집합으로 나눠져 L1과 L2가 같은 집합 상에 없는 것으로 판정되고 2일차에 모두 같은 집합에 들어가게 돼서 2를 출력하고 있었다.

인접한 부분이 'X'(빙판)일 경우 'X'(빙판)를 '.'(물) 으로 바꾸고, 다시 이 공간(빙판이었던 부분)과 인접한 부분이 물이라면 Union을 해주어야 한다.

그 부분이 이 코드에 들어있다.

 if (is_ok(next)) {
                if (Map[next.first][next.second] == 'X') { // 물로 만들어야함
                    Map[next.first][next.second] = '.';
                    Union(now, next);
                    for (int j = 0; j < 4; j++) {
                        pair<int, int> next_next = { next.first + dy[i], next.second + dx[i] };
                        if (is_ok(next_next)) {
                            if (Map[next_next.first][next_next.second] == '.') {
                                if (Find(next) != Find(next_next))
                                    Union(next, next_next);
                            }
                        }
                    }
                    water.push({ next, day + 1 });
                }
}​

종합해서 코드를 짜보면

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 1500 + 5;
char Map[MAX_N][MAX_N];
int R, C;
queue<pair<pair<int, int>, int>> water;
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
pair<int, int> Trace[MAX_N][MAX_N];
pair<int, int> Parent[MAX_N][MAX_N];
 
pair<int, int> Find(pair<int, int> X) {
    if (Parent[X.first][X.second] == X)
        return X;
    return Parent[X.first][X.second] = Find(Parent[X.first][X.second]);
}
 
void Union(pair<int, int> X, pair<int, int> Y) {
    pair<int, int> parent_x = Find(X);
    pair<int, int>parent_y = Find(Y);
    Parent[parent_y.first][parent_y.second] = parent_x;
}
 
 
bool is_ok(pair<int, int>);
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            Parent[i][j] = { i,j };
        }
    }
    pair<int, int> L1, L2;
    bool chk = false;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> Map[i][j];
            if (Map[i][j] == '.')
                water.push({ { i,j }, 0 });
            else if (Map[i][j] == 'L' && !chk) {
                L1 = { i,j };
                water.push({ { i,j }, 0 });
                chk = true;
            }
            else if (Map[i][j] == 'L' && chk) {
                water.push({ { i,j }, 0 });
                L2 = { i,j };
            }
        }
    }
    while (!water.empty()) {
        pair<int, int> now = water.front().first;
        int day = water.front().second;
        water.pop();
        for (int i = 0; i < 4; i++) {
            pair<int, int> next = { now.first + dy[i], now.second + dx[i] };
            if (is_ok(next)) {
                if (Map[next.first][next.second] == 'X') { // 물로 만들어야함
                    Map[next.first][next.second] = '.';
                    Union(now, next);
                    for (int j = 0; j < 4; j++) {
                        pair<int, int> next_next = { next.first + dy[i], next.second + dx[i] };
                        if (is_ok(next_next)) {
                            if (Map[next_next.first][next_next.second] == '.') {
                                if (Find(next) != Find(next_next))
                                    Union(next, next_next);
                            }
                        }
                    }
                    water.push({ next, day + 1 });
                }
                else if (Map[next.first][next.second] == '.') {
                    if (Find(now) != Find(next))
                        Union(now, next);
                }
            }
        }
        if (Find(L1) == Find(L2)) { //인접한 부분을 다 녹인 후, L1과 L2가 같은 집합에 있다면
            cout << day + 1 << "\n";
            break;
        }
    }
    return 0;
}
 
bool is_ok(pair<int, int> now) {
    if (now.first < 0 || now.first >= R || now.second < 0 || now.second >= C)
        return false;
    return true;
}