[Python] 3197 - 백조의 호수 (플래티넘5)

1. 문제 설명

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

3197번: 백조의 호수

Python으로 해결한 사람이 단 한 명밖에 없는 전설의 문제

진짜 순수한 의도로 코드보고 한 수 배우고 싶다.

 

---

2. 아이디어

PyPy로 밀거나 C++같은 언어로 풀면 그렇게 어려운 문제가 아니다.

치즈나 토마토 문제처럼  BFS로 밀어버릴 수 있는 문제다.

문제는 Python으로는 너무 오래 걸린다.

 

대부분은 이 문제를 두 번의 BFS를 무한반복 돌리는 방식으로 해결할 것이다.

'백조가 서로 만날 수 있는가?'를 묻고 안 된다면 얼음을 녹인다. 이걸 될 때까지 반복하는 흐름이다.

하지만 이 방식으로는 절대 Python으로 시간 초과를 벗어날 수 없다.

 

대체 통과한 한 분은 어떤 방법을 쓰신 걸까...존경스럽다.

 

---

3. 코드

import sys
from collections import deque

input = sys.stdin.readline

r, c = map(int, input().split())
swan = []
vector = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def bfs(lake, visited, q_swan:deque):
    next_swan = deque()

    while q_swan:
        y, x = q_swan.popleft()

        if y == swan[1][0] and x == swan[1][1]:
            return True, None

        for q, p in vector:
            m_y = y + q
            m_x = x + p
            if 0 <= m_y < r and 0 <= m_x < c:
                if not visited[m_y][m_x]:
                    visited[m_y][m_x] = 1
                    if lake[m_y][m_x] == "X":
                        next_swan.append([m_y, m_x])
                    else:
                        q_swan.append([m_y, m_x])
    return False, next_swan

def melt(water:deque, lake):
    queue = deque()
    while water:
        y, x = water.popleft()
        for q, p in vector:
            m_y = y + q
            m_x = x + p
            if 0 <= m_y < r and 0 <= m_x < c:
                if lake[m_y][m_x] == 'X':
                    queue.append([m_y, m_x])
                    lake[m_y][m_x] = '.'
    return queue


def solution():
    water = deque()
    lake = []

    for row in range(r):
        new_line = list(input().rstrip())
        for idx, col in enumerate(new_line):
            if col == ".":
                water.append([row, idx])
            if col == "L":
                water.append([row, idx])
                swan.append([row, idx])
        lake.append(new_line)
    
    visited = [[0]*c for _ in range(r)]
    q_swan = deque()

    q_swan.append([swan[0][0], swan[0][1]])
    visited[swan[0][0]][swan[0][1]] = 1
    day = 0
    
    while True:
        is_valid, q_swan = bfs(lake, visited, q_swan)
        if is_valid:
            print(day)
            break
        water = melt(water, lake)
        day += 1 
    
solution()