이번 문제는 단순하게 얼음이 녹는 과정과 백조끼리 만날 수 있는지의 여부를 따로따로 구현하면 시간초과가 발생한다.

백조끼리 만날 수 있는지 확인할 때에 백조가 얼음을 만나면 해당 좌표를 큐에 다음 주기의 백조의 위치로 저장해주어야 한다. 얼음이 녹는 과정의 경우에는 물의 좌표를 모두 저장하고, 물 좌표들을 확인하며 얼음을 만날 때, 얼음을 녹이고, 그 좌표를 새로운 물 큐에 담는다. 이 과정을 통해 방금 물이 된 얼음의 좌표만을 매번 확인하게 되어 시간을 줄일 수 있다.

Code

초기 코드 (시간 초과)

import copy
from collections import deque
r, c = map(int, input().split())
grid = [list(str(input())) for _ in range(r)]
l = []
ices = []
for i in range(r):
    for j in range(c):
        if grid[i][j] == 'L':
            l.append((i, j))
        if grid[i][j] == 'X':
            ices.append((i, j))
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
def melt_ice():
    global ices
    new_grid = copy.deepcopy(grid)
    new_ices = []
    for y, x in ices:
        chk = True
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < r and 0 <= nx < c and new_grid[ny][nx] == '.':
                grid[y][x] = '.'
                chk = False
                break
        if chk:
            new_ices.append((y, x))
    ices = new_ices[:]
def meeting():
    q = deque()
    q.append((l[0][0], l[0][1]))
    visited = [[False for _ in range(c)] for _ in range(r)]
    visited[l[0][0]][l[0][1]] = True
    while q:
        y, x = q.popleft()
        if (y, x) == (l[1][0], l[1][1]):
            return True
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < r and 0 <= nx < c and grid[ny][nx] != 'X' and not visited[ny][nx]:
                q.append((ny, nx))
                visited[ny][nx] = True
    return False
day = 0
while True:
    day += 1
    melt_ice()
    if meeting():
        break
print(day)

정답 코드

from collections import deque
r, c = map(int, input().split())
grid, swan = [], []
water = deque()
for i in range(r):
    tmp = list(str(input()))
    for j in range(c):
        if tmp[j] == '.' or tmp[j] == 'L':
            water.append((i, j))
        if tmp[j] == 'L':
            swan.append((i, j))
    grid.append(tmp)
day = -1
q = deque()
q.append((swan[0][0], swan[0][1]))
visited = [[False for _ in range(c)] for _ in range(r)]
visited[swan[0][0]][swan[0][1]] = True
dy, dx = [-1, 0, 1, 0], [0, -1, 0, 1]

def meet_swan():
    nxt_q = deque()
    while q:
        y, x = q.popleft()
        if (y, x) == (swan[1][0], swan[1][1]):
            return True, None
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < r and 0 <= nx < c and not visited[ny][nx]:
                if grid[ny][nx] == '.' or grid[ny][nx] == 'L':
                    q.append((ny, nx))
                if grid[ny][nx] == 'X':
                    nxt_q.append((ny, nx))
                visited[ny][nx] = True
    return False, nxt_q

def melt_ice():
    nxt_water = deque()
    while water:
        y, x = water.popleft()
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < r and 0 <= nx < c and grid[ny][nx] == 'X':
                nxt_water.append((ny, nx))
                grid[ny][nx] = '.'
    return nxt_water

while True:
    day += 1
    chk, nxt_q = meet_swan()
    if chk:
        break
    water = melt_ice()
    q = nxt_q
print(day)