[BOJ] 3197. 백조의 호수 (💎, BFS/분리집합)

🔗

풀이

💡 아이디어

백조는 자신이 위치한 공간을 포함해 서로 인접해 있는 물 위라면 어디든지 자유롭게 움직일 수 있다. 즉, 두 마리의 백조가 각자 속해 있는 두 개의 물 공간이 서로 만나게 될 때 두 마리의 백조도 만날 수 있다.

1. 서로 인접한 물 공간을 하나의 집합으로 묶기
2. 두 마리의 백조가 속해 있는 집합이 같은 집합인지 확인
3. 물과 맞닿아 있는 빙판 녹이기

우선 초기에는 물 공간의 위치들을 queue 에 저장한다. 해당 물 공간들에 대해서 서로 상하좌우로 인접한 물 공간들에 대해 union-find 알고리즘을 사용하여 하나의 집합으로 묶는다.

서로 인접합 물 공간들에 대해 집합으로 묶는 작업이 끝나면 백조가 만날 수 있는지 확인한다. 확인하는 방법은 두 백조가 같은 집합에 속해있는지 확인하는 것이다. 아래와 같이 확인할 수 있다.

find(백조 1의 위치) == find(백조 2의 위치)

이후 해당 queue 에 저장된 물 공간 위치들을 사용해 맞닿아 있는 빙판의 위치를 새로운 큐인 next_queue 에 저장한다. 여기에 저장되는 값들은 다음 번에 녹아 물 공간이 된다. 이제 next_queue 에 저장된 값을 queue 로 옮기고 1번 과정부터 반복한다.

해당 과정들은 2번에서 두 마리의 백조가 같은 집합에 속하게 될 때까지 반복된다.

참고

최종 코드

# 백조의 호수

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

# 범위 확인 
def is_valid(x, y, target):
    return 0 <= x < R and 0 <= y < C and lake[x][y] in target

# 특정 queue 를 시작으로 bfs
# target 값을 가지면서 방문처리 배열의 값이 second 가 아니여야 함
def bfs(queue, second, target):
    new_queue = deque()
    while queue:
        x, y = queue.popleft()

        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if not is_valid(nx, ny, target) or visited[nx][ny] == second: # bfs 할 때 한 번 방문한 곳을 두 번 방문하면 안 됨
                continue
            visited[nx][ny] = second
            new_queue.append((nx, ny))
            lake[nx][ny] = "."

    return new_queue

def find(x, y):
    if parent[x][y] != (x, y):
        parent[x][y] = find(*parent[x][y])
    return parent[x][y]

def union(x1, y1, x2, y2):
    x1, y1 = parent[x1][y1]
    x2, y2 = parent[x2][y2]
    
    if (x1, y1) < (x2, y2):
        parent[x2][y2] = (x1, y1)
    else:
        parent[x1][y1] = (x2, y2)

# 집합 연결
def make_set(queue, target):
    for x, y in queue:
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if not is_valid(nx, ny, target) or find(x, y) == find(nx, ny): # 한 번 방문했던 곳이어도 같은 집합인지 여부는 확인해야 함
                continue
            union(x, y, nx, ny)

R, C = map(int, input().split())
lake = [list(input()) for _ in range(R)]
visited = [[-1] * C for _ in range(R)]
parent = [[(i, j) for j in range(C)] for i in range(R)]
dx = (0, 1, -1, 0)
dy = (1, 0, 0, -1)

# 초기 물 공간의 위치 모두 찾기
second = 0
queue = deque()
swans = []
for i in range(R):
    for j in range(C):
        if lake[i][j] != 'X':
            visited[i][j] = second
            queue.append((i, j))

            if lake[i][j] == 'L':
                swans.append((i, j))

while True:
    # 집합 만들기
    make_set(queue, [".", "L"])

    # 백조들이 만날 수 있는지 확인 -> 같은 집합인가 
    if find(*swans[0]) == find(*swans[1]):
        break

    second += 1
    queue = bfs(queue, second, ["X"])

print(second)