두개의 큐 BFS - 3197번: 백조의 호수

• 두 큐 BFS: swan_q/swan_next(이동) + water_q/water_next(녹임)로 “경계만” 확장하기
• 입력 시 'L'을 '.'로 치환해서 백조 자리를 물로 처리하기
• 처음부터 물 칸 전부 water_q에 넣어주기
• 녹이기는 visited 없이 진행: 'X' -> '.'로 바꾸는 순간 1회만 큐에 push하게 됨
• 백조 BFS: visited를 한 번만 만들고 재사용하기, 오늘의 물은 swan_q, 얼음은 swan_next에 넣기
  -> 각 칸을 최대 한두 번만 처리 → 총 O(R·C), 매일 전체 스캔/visited 재생성은 시간초과!

import sys
from collections import deque


input = sys.stdin.readline

r, c = map(int, input().split())

maps = []

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

swans = []
water_q = deque()
water_next = deque()

for i in range(r):
    line = list(input().rstrip("\n"))

    for j in range(len(line)):
        if line[j] != "X":
            water_q.append((i, j))
        if line[j] == "L":
            swans.append((i, j))
            line[j] = "."  # 백조 자리 물로 바꾸기

    maps.append(line)


a1, b1 = swans[0][0], swans[0][1]  # 첫번째 백조 좌표
a2, b2 = swans[1][0], swans[1][1]  # 두번째 백조 좌표

swan_q = deque([(a1, b1)])  # 첫번째 백조 넣기
swan_next = deque()

visited = [[False] * c for _ in range(r)]
visited[a1][b1] = True


def swan_meet_check():

    while swan_q:
        i, j = swan_q.popleft()

        if (i, j) == (a2, b2):
            return True

        for k in range(4):
            ni, nj = i + dx[k], j + dy[k]

            if 0 <= ni < r and 0 <= nj < c and not visited[ni][nj]:
                visited[ni][nj] = True

                if maps[ni][nj] == ".":  # 물이면 오늘 이동
                    swan_q.append((ni, nj))
                else:  # 얼음이면 내일 녹은 후 이동
                    swan_next.append((ni, nj))

    return False


def ice_melting():

    while water_q:
        i, j = water_q.popleft()

        for k in range(4):
            ni, nj = i + dx[k], j + dy[k]

            if (
                0 <= ni < r
                and 0 <= nj < c
                and maps[ni][nj] == "X"
                and not visited[ni][nj]
            ):
                maps[ni][nj] = "."
                water_next.append((ni, nj))

    return


day_cnt = 0


while True:
    if swan_meet_check():
        break

    ice_melting()
    # 내일을 위해 바꾸기
    water_q, water_next = water_next, deque()
    swan_q, swan_next = swan_next, deque()

    day_cnt += 1


print(day_cnt)