boj 골드 1

시간제한이 까다로웠다. Python3으로 통과한 사람이 한 명도 없었다.
PyPy3 풀이를 찾아보니 각 빙하가 녹는 시간을 찾고 + 파라메트릭 서치로 찾았다.

원래 내 풀이

import sys
input = sys.stdin.readline
from collections import deque
import math
swan = set() # 백조가 있는 공간
start = 0
nrow, ncol = list(map(int, input().split()))
board = []

for y in range(nrow):
    ar = (list(input().strip()))
    board.append(ar)
    if start == 0:
        for x in range(len(ar)):
            if ar[x] == 'L':
                start = y,x





def findMelted(y,x):

    v = deque([])
    newlyAdded = set()

    v.append((y,x))
    swan.add((y,x))
    newlyAdded.add((y,x))

    while v:
        y,x = v.popleft()
        for dy, dx in zip([1, -1, 0, 0], [0, 0, 1, -1]):
            if 0 <= y + dy < nrow and 0 <= x + dx < ncol and (y+dy,x+dx) not in swan:
                if board[y+dy][x+dx]=='.' :
                    swan.add((y+dy, x+dx))
                    v.append((y+dy, x+dx))
                elif board[y+dy][x+dx] == 'X':
                    newlyAdded.add((y+dy,x+dx))
                elif board[y+dy][x+dx] == 'L':
                    return 'f'

    return newlyAdded

y,x = start
board[y][x] = '.'
nxt = findMelted(y,x)


day = 0
f = 'a'
while True:
    ice = set() # 다음 얼음 깨기
    for y,x in nxt:
        f = findMelted(y,x)
        if f == 'f':
            break
        ice.update(f)
    day += 1
    if f == 'f':
        break

    nxt = ice

print(math.ceil(day/2))

nxt 에 새롭게 녹은 얼음 좌표들을 넣고 계속해서 얼음을 녹여가서 다른 swan 을 찾을때까지 녹여간 후 양방향에서 녹았을 것이므로 걸린 날짜day/2를 올림하는 것.

다른 풀이를 보니 일단 전체 얼음이 녹는 시간을 다 구해준 후 bfs로 푸는 방법이 있긴 하더라. 방문한 곳을 다시 방문하지 않아도 되게 하는 것이 관건이었던 것 같다.