[Platinum V] 백조의 호수 - 3197

문제 링크

성능 요약

메모리: 255312 KB, 시간: 1200 ms

분류

너비 우선 탐색, 자료 구조, 분리 집합, 그래프 이론, 그래프 탐색

문제 설명

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

호수는 행이 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'은 백조가 있는 공간으로 나타낸다.

출력

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

---

문제 풀이

문제 분석

두 마리 백조가 호수에 있고, 호수는 얼음과 물로 이루어져 있습니다. 얼음은 매일 물과 접촉한 부분이 녹습니다. 두 백조가 만나는 데 걸리는 최소 날짜 수를 구해야 합니다. 입력은 호수의 크기(R, C)와 호수의 상태(얼음 'X', 물 '.', 백조 'L')입니다. 출력은 두 백조가 만나는 데 걸리는 날짜 수입니다.

접근 방법

이 문제는 BFS(너비 우선 탐색)를 활용하여 해결할 수 있습니다. 핵심은 다음과 같습니다.

1. 얼음 녹이기: 매일 얼음을 녹이는 과정을 BFS로 구현합니다. 물과 접촉한 얼음을 녹이는 것을 시뮬레이션합니다.
2. 백조 이동: 백조가 이동 가능한 경로를 BFS로 탐색합니다. 매일 얼음이 녹은 후, 백조가 다른 백조에게 도달할 수 있는지 확인합니다. 이때, 다음 날에 이동할 수 있는 위치를 미리 저장해두는 것이 중요합니다.
3. 날짜 계산: 백조가 만날 때까지 얼음 녹이기와 백조 이동을 반복하며 날짜를 증가시킵니다.

분리 집합(Disjoint Set) 자료구조를 사용할 수도 있지만, 주어진 문제의 크기(R, C <= 1500)에서는 BFS만으로도 충분히 효율적인 풀이가 가능합니다. 이 코드에서는 BFS를 사용하여 얼음을 녹이고, 백조의 이동 가능성을 탐색합니다.

구현 설명

1. 초기 설정

• graph: 호수의 상태를 나타내는 2차원 리스트입니다. 'X'는 얼음, '.'은 물, 'L'은 백조를 의미합니다.
• duck: 백조의 위치를 저장하는 리스트입니다.
• start: 물과 접촉한 얼음의 위치를 저장하는 deque입니다. 처음에 모든 물 위치를 start에 넣어 초기화합니다. 이 위치들을 시작으로 BFS를 수행하여 얼음을 녹입니다.
• duckqueue: 백조가 현재 이동 가능한 위치를 저장하는 deque입니다.
• visited: 백조가 방문한 위치를 추적하는 2차원 boolean 리스트입니다.
• day: 경과한 날짜 수를 저장하는 변수입니다.

2. 얼음 녹이기 (BFS 함수)

• BFS(graph) 함수는 start 큐에 저장된 위치에서 시작하여 BFS를 수행합니다.
• start 큐에서 좌표를 하나씩 꺼내어 상하좌우 인접한 위치를 확인합니다.
• 인접한 위치가 얼음('X')이고, 아직 녹지 않았다면, 해당 위치를 stack 큐에 추가하고 얼음에서 물로 바꿉니다. 이 stack은 다음 날 녹을 얼음의 위치를 저장하는 역할을 합니다.
• BFS가 끝나면, start 큐를 stack 큐로 갱신합니다. 이렇게 하면 다음 날에 녹을 얼음 위치를 기준으로 BFS를 시작할 수 있습니다.

3. 백조 이동 (while not found 루프)

• duckqueue에서 좌표를 하나씩 꺼내어 상하좌우 인접한 위치를 확인합니다.
• 만약 인접한 위치가 다른 백조의 위치와 같다면, found를 True로 설정하고 루프를 종료합니다.
• 인접한 위치가 물('.')이고, 아직 방문하지 않았다면, duckqueue에 추가합니다.
• 인접한 위치가 얼음('X')이고, 아직 방문하지 않았다면, duckqueue2에 추가합니다. duckqueue2는 다음 날 백조가 이동할 수 있는 위치를 저장합니다.
• duckqueue가 비어있지만 found가 False라면, 얼음을 녹이고 날짜를 증가시킵니다. 그리고 duckqueue를 duckqueue2로 갱신합니다.

4. 결과 출력

• found가 True가 되면, 두 백조가 만나는 날짜(day - 1)를 출력합니다. day - 1인 이유는 마지막 날짜가 증가한 후에 백조가 만났기 때문입니다.

⏱복잡도 분석

• 시간 복잡도:
  • 얼음을 녹이는 BFS는 최악의 경우 모든 칸을 방문하므로 O(R*C)입니다.
  • 백조가 이동 가능한지 확인하는 BFS 역시 최악의 경우 모든 칸을 방문하므로 O(R*C)입니다.
  • 두 BFS를 수행하는 while 루프는 최대 R*C번 반복될 수 있습니다 (모든 얼음이 녹을 때까지).
  • 따라서 전체 시간 복잡도는 O((R*C)^2)가 됩니다. 하지만, 실제로는 모든 칸이 얼음인 경우는 드물기 때문에, 평균적으로는 이보다 훨씬 빠릅니다.
• 공간 복잡도:
  • graph는 O(R*C)의 공간을 사용합니다.
  • visited는 O(R*C)의 공간을 사용합니다.
  • duckqueue, duckqueue2, start는 최악의 경우 O(R*C)의 공간을 사용합니다.
  • 따라서 전체 공간 복잡도는 O(R*C)입니다.

핵심 포인트

1. 두 개의 BFS: 얼음을 녹이는 BFS와 백조의 이동 가능성을 확인하는 BFS를 분리하여 구현합니다.
2. 다음 날 이동 가능 위치 저장: 백조가 현재 날짜에 이동할 수 없는 얼음 위치를 큐에 저장해두었다가, 다음 날 얼음이 녹으면 해당 위치에서 탐색을 시작합니다.
3. 날짜 계산: 백조가 만나는 시점을 정확하게 판단하기 위해, 날짜를 증가시키는 시점을 주의 깊게 관리해야 합니다. 마지막에 day - 1을 출력하는 이유를 이해하는 것이 중요합니다.

풀이 코드

import sys
from collections import deque

def BFS(graph):
    global start
    directions = [(0,1),(0,-1),(1,0),(-1,0)]
    stack = deque()
    
    n= len(graph)
    m = len(graph[0])
    while start:
        x,y = start.popleft()
        for dx,dy in directions:
            sx, sy = x+dx,y+dy
            if 0<=sx<n and 0<=sy<m:
                if graph[sx][sy] == "X":
                    stack.append((sx,sy))
                    graph[sx][sy] = "."

    start = stack

graph = []
n,m = map(int,sys.stdin.readline().split())

for i in range(n):
    graph.append(list(sys.stdin.readline().strip()))


duck = []

start = deque()
day = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] != "X":
            start.append((i,j))
        if graph[i][j] == "L":
            duck.append((i,j))

duckqueue = deque()
duckqueue.append(duck[0])
visited = [[False]*m for i in range(n)]
visited[duck[0][0]][duck[0][1]] = True
duckqueue2 = deque()

day = 0
found = False
directions = [(0,1), (0,-1), (1,0), (-1,0)]

while not found:
    while duckqueue:
        x, y = duckqueue.popleft()
        if (x, y) == duck[1]:
            found = True
            break
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                visited[nx][ny] = True
                if graph[nx][ny] == '.':
                    duckqueue.append((nx, ny))
                else:
                    duckqueue2.append((nx, ny))
    if found:
        print(day-1)
        break

    BFS(graph)
    day += 1

    duckqueue = duckqueue2
    duckqueue2 = deque()