백준 3197: 백조의 호수 - BFS

https://www.acmicpc.net/problem/3197

3197번: 백조의 호수

python3로 돌릴 경우 시간초과가 나기 때문에 pypy3로 제출하였습니다.

 

이 문제는 아무 생각 없이 BFS를 돌리게 되면 시간 초과가 납니다.

우선 백조가 만나는 지 체크하는 것과, 물을 녹이는 것을 한 주기라고 생각합니다.

queue를 몇 개 더 추가하여, 물을 녹이기 전 백조가 만나는 지 체크하고, 만나지 않는 다면 물을 녹이는 일을 하 되, 다음 주기 때의 좌표들을 주기 마다 저장을 해야합니다.

그래야 이전 주기 때 체크했던 것들을 다시 체크해야 하는 상황을 피할 수 있습니다. 

이 부분을 신경 써서 문제를 푼다면 시간 초과를 해결할 수 있습니다.

 

제가 사용했던 queue는 다음과 같습니다.

 

• queue - 백조가 다른 백조를 찾을 때 사용하는 queue
• next_queue - 백조가 'X'를 만나면 추후에 물을 녹인 후 확인 할 queue
• water - 물의 좌표를 담는 queue, 상하좌우에 X가 있는지 확인해야함
• next_water - 빙판을 녹여서 물로 만든 좌표를 다음 주기 때 다시 상하좌우에 'X'가 있는지 체크해야하므로, 그 정보를 담은 queue

그 후에 한 주기가 끝나면, 'queue = next_queue', 'water = next_water'을 해줍니다.

그렇게 되면 이전에 백조가 주기마다 처음 백조의 위치에서부터 시작할 필요가 없습니다. 또한 물도 빙산을 찾아 녹이기 위해 상하좌우를 이미 체크했던 좌표를 다시 체크하지 않게 됩니다.

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

dy = (-1, 0, 1, 0)
dx = (0, -1, 0, 1)

def find_swan(lake, visited, queue):
    next_queue = deque()
    while queue:
        y, x  = queue.popleft()
        if y == swan[1][0] and x == swan[1][1]:
            return True, None
        
        for ii in range(4):
            ny = y + dy[ii]
            nx = x + dx[ii]
            if not 0 <= ny < row or not 0 <= nx < column:
                continue
            if visited[ny][nx]:
                continue
            if lake[ny][nx] == 'X':
                next_queue.append((ny, nx))
            else:
                queue.append((ny, nx))
            visited[ny][nx] = True

    return False, next_queue

def melt_ice(water, lake):
    next_water = deque()
    while water:
        y, x = water.popleft()
        for ii in range(4):
            ny = y + dy[ii]
            nx = x + dx[ii]
            if not 0 <= ny < row or not 0 <= nx < column:
                continue
            if lake[ny][nx] == 'X':
                next_water.append((ny, nx))
                lake[ny][nx] = '.'
    
    return next_water


row, column = map(int, input().split())
lake = []
swan = []
water = deque()

for rr in range(row):
    current_lake_info = list(input().rstrip())
    for cc, vv in enumerate(current_lake_info):
        if vv == '.' or vv == 'L':
            water.append((rr, cc))
        if vv == 'L':
            swan.append((rr, cc))
    lake.append(current_lake_info)

day = -1
visited = [[False for _ in range(column)] for _ in range(row)]
queue = deque()

y, x = swan[0][0], swan[0][1]
queue.append((y, x))
visited[y][x] = True

while True:
    day += 1
    found, next_queue = find_swan(lake, visited, queue)
    if found:
        break
    water = melt_ice(water, lake)
    queue = next_queue

print(day)