[ 백준 / 파이썬 ] 플레티넘 5 - 3197. 백조의 호수

난이도

문제

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

아래에는 세 가지 예가 있다.

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

출력
첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

예제

입력	출력
10 2 .L .. XX XX XX XX XX XX .. .L	3

입력	출력
4 11 ..XXX...X.. .X.XXX...L. ....XXX..X. X.L..XXX...	2

입력	출력
8 17 ...XXXXXX..XX.XXX ....XXXXXXXXX.XXX ...XXXXXXXXXXXX.. ..XXXXX.LXXXXXX.. .XXXXXX..XXXXXX.. XXXXXXX...XXXX... ..XXXXX...XXX.... ....XXXXX.XXXL...	2

풀이

우선 문제만 보면 간단한 BFS 문제처럼 보였고, 핵심 동작도 BFS가 맞다.
다만, 난이도가 높은 이유는 효율적으로 BFS를 탐색해야하고, 불필요한 공간을 낭비해서는 안된다.

일반적으로 백조 BFS 탐색, 얼음 BFS로 녹이기 는 시간초과가 발생한다.

그래서 이 글을 읽고 BFS를 어떻게 활용해야 시간을 단축하고 메모리를 적게 사용할 수 있는지 알게 됐다.

동작 원리는 간단하다.

1. 백조는 물에서만 이동할 수 있다.
2. 물에 근접한 얼음은 다음 날이 되면 물로 녹는다.

여기서 문제에 대한 힌트를 찾아야 한다.

백조는 물에서만 이동할 수 있는데, 물에 근접한 얼음은 다음 날이 되면 물로 변한다는 것은 백조가 이동할 수 있는 곳 중 얼음인 곳은 백조의 다음 날 위치가 되는 것이다.

그러면 다음 날이 되었을 때, 전날 찾아뒀던 백조의 위치에서 탐색을 하고 이것을 반복하면 백조를 만날 수 있게 된다.

이러한 방법은 백조를 탐색할 때, 중복되는 탐색을 방지 할 수 있고 효율적으로 정답 가능성이 있는 곳만 탐색하게 된다.

따라서 총 네개의 큐가 필요하고, 이것을 이용해서 문제를 해결한다.

코드

from sys import stdin
from collections import deque

input = stdin.readline
directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]


def meet_swan(swan, next_swan, target, R, C, lake, swan_visited):
    global directions
    while swan:
        y, x = swan.popleft()

        for dy, dx in directions:
            ny, nx = y + dy, x + dx
            if (ny, nx) == target:
                return True


            if 0 <= ny < R and 0 <= nx < C and not swan_visited[ny][nx]:
                if lake[ny][nx] == '.':
                    swan.append((ny, nx))
                elif lake[ny][nx] == 'X':
                    next_swan.append((ny, nx))
                swan_visited[ny][nx] = True

    return False


def melt(water, next_water, R, C, lake, water_visited):
    global directions

    while water:
        y, x = water.popleft()
        lake[y][x] = '.'

        for dy, dx in directions:
            ny, nx = y + dy, x + dx

            if 0 <= ny < R and 0 <= nx < C and not water_visited[ny][nx]:
                if lake[ny][nx] == '.':
                    water.append((ny, nx))
                elif lake[ny][nx] == 'X':
                    next_water.append((ny, nx))
                water_visited[ny][nx] = True


def solution():
    R, C = map(int, input().split())
    lake = [list(input().rstrip()) for _ in range(R)]
    swan_visited = [[False for _ in range(C)] for _ in range(R)]
    water_visited = [[False for _ in range(C)] for _ in range(R)]

    swan = deque()
    next_swan = deque()
    water = deque()
    next_water = deque()
    target = ()
    for y in range(R):
        for x in range(C):
            if lake[y][x] == '.':
                water.append((y, x))
                water_visited[y][x] = True
            elif lake[y][x] == 'L':
                water.append((y, x))
                water_visited[y][x] = True
                if not swan:
                    swan.append((y, x))
                    swan_visited[y][x] = True
                else:
                    target = (y, x)
    answer = 0
    while True:
        melt(water, next_water, R, C, lake, water_visited)

        if meet_swan(swan, next_swan, target, R, C, lake, swan_visited):
            break



        water = next_water
        swan = next_swan
        next_water = deque()
        next_swan = deque()

        answer += 1

    print(answer)
    
solution()