백준 3197 백조의 호수

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/3197

이 문제는 2차원 그래프에 백조(L), 물(.), 얼음(X)이 있고, 하루가 지날 때마다 물이 주위에 있는 얼음을 녹여나가고, 백조는 물 위를 움직일 수 있다고 할 때, 2마리의 백조가 최소 몇 일 안에 만날 수 있는지 찾는 문제이다.

풀이

난이도 : Platinum V

처음에 하루마다 물 주변으로 얼음을 녹이는 것을 bfs로 해결하려고 하였고, 그 때마다 백조끼리 연결되어 있는 것을 어떤 방법으로 확인할 지 고민하였다.
이후에 union-find (분리 집합) 방식을 떠올렸고, 물로 되어 있는 부분은 parent가 같도록 설정하여 하루가 지날 때마다 백조의 parent가 같은 지 확인하는 방법으로 해결방안을 설계하였다.

1) 처음에는 queue에 물 좌표를 모두 저장
2) 초기에 물끼리 연결된 부분 union_parent
3) 처음부터 백조끼리 만날 수 있는 경우 0 출력 후 종료
4) q에서 데이터를 하나씩 꺼내면서 bfs
5) bfs를 진행하면서 물이 연결되어 있는지 확인하고 union_parent
6) 날짜가 바뀔 때마다 백조끼리 연결되어 있는지 확인 (find_parent)

• graph : 2차원 배열 (물, 얼음, 백조 정보)
• parent : graph를 1차원으로 놓아 부모를 저장하는 배열
• l1_x, l1_y, l2_x, l2_y : 백조가 있는 좌표
• q : bfs 할 때 사용할 deque로 (x 좌표, y 좌표, 현재 날짜) 저장

✔ 주의할 점

• 이 풀이는 백준에서 python3로 제출하면 시간초과 결과가 발생하므로 pypy3로 제출해야 한다.

코드

from collections import deque
import sys

# 분리 집합 메소드 (find, union)
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = parent[a]
    else:
        parent[a] = parent[b]


# 데이터 입력 및 초기화 (parent는 2차원 배열(graph)을 1차원으로 붙여놓은 형태)
input = sys.stdin.readline
r, c = map(int, input().split())
parent = [i for i in range(r * c)]
q = deque()
l1_x, l1_y, l2_x, l2_y = -1, -1, -1, -1

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

graph = []
for _ in range(r):
    graph.append(list(str(input())))


# 초기 queue와 parent 설정
for i in range(r):
    for j in range(c):
        # 얼음일 경우 continue
        if graph[i][j] == 'X':
            continue
        
        # 백조 좌표 기록
        if graph[i][j] == 'L':
            if l1_x != -1:
                l2_x, l2_y = i, j
            else:
                l1_x, l1_y = i, j

        # 물 좌표 q에 저장
        q.append((i, j, 0))

        # 물끼리 연결되어 있다면 union
        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            
            if nx < 0 or ny < 0 or nx >= r or ny >= c:
                continue
            
            if graph[nx][ny] == 'X':
                continue
            if find_parent(parent, i * c + j) != find_parent(parent, nx * c + ny):
                union_parent(parent, i * c + j, nx * c + ny)

# 처음부터 연결되어 있을 경우 정답 출력 후 종료
if find_parent(parent, l1_x * c + l1_y) == find_parent(parent, l2_x * c + l2_y):
    print(0)
    exit(0)

# q : (x 좌표, y 좌표, 현재 날짜), prvious : 이전 날짜
previous = 0
while q:
    x, y, now = q.popleft()

    # 날짜가 바뀌는 경우, 백조끼리 연결되어 있는지 확인
    if previous != now:
        previous = now
        if find_parent(parent, l1_x * c + l1_y) == find_parent(parent, l2_x * c + l2_y):
            print(previous)
            break
    
    # 주변 탐색
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if nx < 0 or ny < 0 or nx >= r or ny >= c:
            continue
        
        # 얼음으로 되어 있을 경우 얼음을 깨고, q에 넣어주기
        if graph[nx][ny] == 'X':
            graph[nx][ny] = '.'
            q.append((nx, ny, now + 1))

        # 주변 탐색한 값에서 다시 한 번 주위 값이랑 비교하여 물로 연결되어 있다면 union_parent 수행
        for j in range(4):
            nx2 = nx + dx[j]
            ny2 = ny + dy[j]

            if nx2 < 0 or ny2 < 0 or nx2 >= r or ny2 >= c:
                continue
            if graph[nx2][ny2] == '.':
                union_parent(parent, nx * c + ny, nx2 * c + ny2)

# bfs 반복문 안에서 답을 찾지 못하였을 경우, 마지막에 얼음을 깨면서 만난 것이므로 정답 출력
if not q and find_parent(parent, l1_x * c + l1_y) == find_parent(parent, l2_x * c + l2_y):
    print(previous)