[bj3197] 백조의 호수

문제

• 백준 URL: 백조의 호수
• 난이도: 플래티넘 5

풀이

가장 먼저, 문제의 첫 번째 문장에서 '두 마리의 백조가 호수에서 살고 있으며', '두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다'고 되어 있기 때문에 L은 두 개만 존재하며 두 개의 L이 바로 만나게되는 케이스는 존재하지 않는다고 가정하고 풀이하였다.

이 문제의 핵심은 BFS를 수행할 때 탐색한 부분을 다시 탐색하지 않도록 하는 것이다.
만약 풀이를 다음과 같은 방식으로 한다고 생각해보자.
1. 전체 호수에 대해 BFS를 수행하여 백조가 만날 수 있는지 확인한다.
2. 만약 만날 수 없다면 전체 호수에 대해 BFS를 수행하여 빙판을 녹인다
3. 다시 1로 돌아가 백조가 만날 때까지 반복한다.

이와 같은 방식을 사용하면 당연하게도 시간 초과가 발생한다.
따라서 다음과 같은 방식을 사용해야 한다.
1. 백조의 이동 시작 지점에 대해 BFS를 수행한다. 만약 백조가 만날 수 있다면 코드가 종료될 것이다. 만약 만날 수 없다면, 시작 지점에서 이동 가능한 모든 지점을 탐색하고 빙판과 만나는 좌표에 대해 다음 이동 시작 지점 리스트에 추가한다.
2. 물 좌표에 대해 빙판과 만나는지 체크하고 빙판을 녹인다. 이 때, 처음 1회차는 존재하는 모든 물 좌표에 대해 확인하는 작업을 거치게 되지만 다음 회차부터는 빙판과 만나서 녹은 지점에 대해서만 검사한다. (왜냐하면 다음에 녹을 빙판은 무조건 이번 회차에 녹은 빙판과 인접하기 때문이다.)

이를 다음과 같이 두 개의 함수를 통해 구현하였다.

def find_swan(q):
    swan_next = deque()
    while q:
        x,y = q.popleft()
        if (x,y) == swan_l[1]: return False
        for dx,dy in di:
            nx,ny = x+dx,y+dy
            if 0 <= nx < r and 0 <= ny < c and not visited[nx][ny]:
                if board[nx][ny] == 'X':
                    swan_next.append((nx,ny))
                else: q.append((nx,ny))
                visited[nx][ny] = 1
    return swan_next
            
def melt(q):
    water_next = deque()
    while q:
        x,y = q.popleft()
        for dx,dy in di:
            nx,ny = x+dx,y+dy
            if 0 <= nx < r and 0 <= ny < c:
                if board[nx][ny] == 'X':
                    board[nx][ny] = '.'
                    water_next.append((nx,ny))
    return water_next

find_swan() 함수는 백조가 만날 수 있는지 검사하는 함수이며, 백조의 다음 이동 시작 지점을 반환한다.
melt() 함수는 빙판을 녹이는 함수이며, 다음 회차에 빙판과 인접해있는 물 좌표의 리스트를 반환한다.

전체 코드

from collections import deque

r,c = map(int, input().split())
board = [list(input()) for _ in range(r)]
visited = [[0]*c for _ in range(r)]
swan_l = []
water = deque()
days = 0
di = [(1,0),(-1,0),(0,1),(0,-1)]

for i in range(r):
    for j in range(c):
        if board[i][j] == 'L':
            swan_l.append((i,j))
        if board[i][j] in ['.', 'L']:
            water.append((i,j))
            
def find_swan(q):
    swan_next = deque()
    while q:
        x,y = q.popleft()
        if (x,y) == swan_l[1]: return False
        for dx,dy in di:
            nx,ny = x+dx,y+dy
            if 0 <= nx < r and 0 <= ny < c and not visited[nx][ny]:
                if board[nx][ny] == 'X':
                    swan_next.append((nx,ny))
                else: q.append((nx,ny))
                visited[nx][ny] = 1
    return swan_next
            
def melt(q):
    water_next = deque()
    while q:
        x,y = q.popleft()
        for dx,dy in di:
            nx,ny = x+dx,y+dy
            if 0 <= nx < r and 0 <= ny < c:
                if board[nx][ny] == 'X':
                    board[nx][ny] = '.'
                    water_next.append((nx,ny))
    return water_next

swan = deque([(swan_l[0])])
while 1:
    if not (swan:=find_swan(swan)):break
    water = melt(water)
    days+=1
print(days)