BOJ 3197 - 백조의 호수 링크
(2023.09.27 기준 P5)

문제

두 마리의 백조가 호수에서 살고 있으며, 호수는 물이나 얼음인 칸으로 이루어져 있다.
매일 물은 인접한 얼음인 칸을 녹인다. 백조가 만나기 위한 최소 일수 출력

알고리즘

BFS & 분리 집합

풀이

백조가 속해 있는 물 공간에서는 자유롭게 움직일 수 있다. 두 백조가 만나기 위해선 결국, 두 백조가 속해 있는 물 공간이 만나야 한다는 뜻이 된다.

물은 인접한 빙판을 녹인다. 녹이는 시간은 하루. 이는 BFS를 사용하면 된다.

하나의 물 공간은 곧, 하나의 집합이다. 분리 집합을 사용하여 물인 공간은 하나의 집합으로 만들고, BFS를 돌리면서 물과 인접한 빙판은 물과 union하면 된다.

그런데, 녹이면서 union하고 두 백조의 집합이 같은 집합인지 판별하게 되면 아마, 첫 TC에서 WA를 받을 것이다. 왜냐면, 두 영역이 맞닿는 순간에 union을 하지 않기 때문. 그렇다고 또 인접 공간과 union을 시도하면 TLE를 받을 것이다.

그러므로, union -> set check -> bfs 순으로 진행하는 것이 좋다.

union 단계에선 현재 dq에 있는 위치들의 인접한 공간 중 물인 곳과 union해주고
set check 단계에선 두 백조의 집합이 같은지 확인하고
bfs 단계에선 방금 물이 된 곳부터 인접한 빙판으로 나아가면 된다. (visited 체크만 해주면 물과 빙판을 구별할 수 있다.)

코드

• C++

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1500 * 1500;
const pii dir[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int R, C, pa[MAXN];

// 2차원 좌표를 1차원 좌표로 변경
int coord(int i, int j){
    return i * C + j;
}

// union-find
int find(int u){
    if (pa[u] != u) pa[u] = find(pa[u]);
    return pa[u];
}

void merge(int u, int v){
    u = find(u);
    v = find(v);
    if (u < v) pa[v] = u;
    else if (v < u) pa[u] = v;
}

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

    cin >> R >> C;
    string matrix[R]; for (int i = 0; i < R; i++) cin >> matrix[i];

    // 물과 백조가 있는 공간을 dq에 넣자.
    deque<pii> dq;
    bool visited[R][C]; fill(&visited[0][0], &visited[R - 1][C], false);
    vector<pii> swans; // 백조가 있는 위치
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) if (matrix[i][j] != 'X'){
        dq.push_back({i, j});
        visited[i][j] = true;
        if (matrix[i][j] == 'L') swans.push_back({i, j}); // 백조가 있는 공간은 따로 저장
    }

    // 두 백조가 있는 영역이 합쳐지는 것은 분리 집합으로 판별할 수 있다.
    iota(pa, pa + R * C, 0);

    // BFS & disjoint set
    int days = 0; // 걸리는 날
    while (!dq.empty()){

        // 1. 현재 dq에 담겨있는 위치에서 인접한 위치 중 물인 공간과 union
        for (auto [i, j]: dq){
            int u = coord(i, j);
            for (auto [di, dj]: dir)
                if (0 <= i + di && i + di < R && 0 <= j + dj && j + dj < C && visited[i + di][j + dj]){ // 방문됨은 즉, 물인 공간
                    int v = coord(i + di, j + dj);
                    merge(u, v);
                }
        }

        // 2. 두 백조가 같은 집합에 속하는 지 확인
        if (find(coord(swans[0].x, swans[0].y)) == find(coord(swans[1].x, swans[1].y))){
            cout << days;
            break;
        }
        days++; // 다음 단계에서 빙판이 녹으면서 하루가 지난다.

        // 3. 물과 인접해 있는 빙판을 녹이면서, 녹인 빙판의 위치를 dq에 담기
        for (int sz = dq.size(); sz; sz--){
            auto [i, j] = dq.front(); dq.pop_front();
            for (auto [di, dj]: dir)
                if (0 <= i + di && i + di < R && 0 <= j + dj && j + dj < C && !visited[i + di][j + dj]){ // 방문됨은 즉, 물인 공간
                    dq.push_back({i + di, j + dj});
                    visited[i + di][j + dj] = true;
                }
        }
    }
}

• Python

import sys; input = sys.stdin.readline
from collections import deque

dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# 2차원 좌표를 1차원 좌표로 변경
def coord(i, j):
    return i * C + j

# union-find
def find(u):
    if pa[u] != u:
        pa[u] = find(pa[u])
    return pa[u]

def union(u, v):
    u = find(u)
    v = find(v)
    if u < v:
        pa[v] = u
    elif v < u:
        pa[u] = v

R, C = map(int, input().split())
matrix = [input().strip() for _ in range(R)]

# 물과 백조가 있는 공간을 dq에 넣자.
dq = deque()
visited = [[False] * C for _ in range(R)]
swans = [] # 백조가 있는 위치
for i in range(R):
    for j in range(C):
        if matrix[i][j] != 'X':
            dq.append((i, j))
            visited[i][j] = True
            if matrix[i][j] == 'L': # 백조가 있는 공간은 따로 저장
                swans.append((i, j))

# 두 백조가 있는 영역이 합쳐지는 것은 분리 집합으로 판별할 수 있다.
pa = [i for i in range(R * C)]

# BFS & disjoint set
days = 0 # 걸리는 날
while dq:

    # 1. 현재 dq에 담겨있는 위치에서 인접한 위치 중 물인 공간과 union
    for i, j in dq:
        u = coord(i, j)
        for di, dj in dir:
            if 0 <= i + di < R and 0 <= j + dj < C and visited[i + di][j + dj]: # 방문됨은 즉, 물인 공간
                v = coord(i + di, j + dj)
                union(u, v)

    # 2. 두 백조가 같은 집합에 속하는 지 확인
    if find(coord(*swans[0])) == find(coord(*swans[1])):
        print(days)
        break
    days += 1 # 다음 단계에서 빙판이 녹으면서 하루가 지난다.

    # 3. 물과 인접해 있는 빙판을 녹이면서, 녹인 빙판의 위치를 dq에 담기
    for _ in range(len(dq)): # 현재 담겨져 있는 위치들만 BFS
        i, j = dq.popleft()
        for di, dj in dir:
            if 0 <= i + di < R and 0 <= j + dj < C and not visited[i + di][j + dj]:
                dq.append((i + di, j + dj))
                visited[i + di][j + dj] = True