[BOJ] 백준 3197 백조의 호수 Python

3197번: 백조의 호수

문제

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

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

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

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

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      처음               첫째 날             둘째 날

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

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

입력

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

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

---

문제풀이
첫번째, 호수의 얼음과 물에 대한 접근방식은 물(.)이 있는 구역마다 BFS를 통해 주위 얼음을 녹이면 되지 않을까라고 생각했다. 하지만 더 꼼꼼히 문제를 해석했을때 1번백조와 2번백조를 만나게만 하면 되므로 1번백조의 구역에서의  얼음을 녹이며 BFS를 진행시키면 길찾기 문제처럼 백조끼리 만나게 할 수 있다.
이를 위해서는 원래의 호수정보와 다음단계 호수정보가 필요했다. 다음단계 호수정보를 구하고 원래의 호수정보에 대입시켜 계속 진행시키면 결국 백조가 며칠이 지났을때 만날 수 있는지 계산할 수 있다. 
두번째, 백조가 며칠이 지났을때 만날 수 있냐? 라고 물어보는 말인 즉슨, 호수의 업데이트 + 백조의 만남 여부확인 → 1cycle 이라는 의미로 해석되었다.
따라서 이 두 가지의 문제를 해결하기 위해 방안을 BFS기반의 방안을 고민하였다.
큐는 아래와 같이 네개를 만들었다.

변수해석
queue : 1번 백조의 위치로부터 시작하는 BFS 길찾기를 위한 큐
n_queue : 녹아질 얼음이 담겨 있는 큐
water : 현재 물이 얼음을 녹인 진척도가 담긴 큐
n_water : 얼음이 녹아진 좌표가 담긴 큐

문제풀이순서
1. 호수를 입력받으며 물(.), 백조(L)은 water 큐에 저장하고 백조(L)의 위치는 swan 리스트에 따로 한번 더 저장시킨다.
2. 1번 백조의 위치를 추출해서 그 좌표의 위치로부터 queue에 넣고 find_swan(백조의 만남 여부찾기)를 진행시킨다. 반환값은 queue의 BFS를 통해 백조가 만날 수 있는지와 녹아질 얼음이 담겨진 큐(n_queue)이다.
3. 만약 만났다면 무한 루프 반복문을 깨고 iteration_count를 출력.
4. 아니라면 melt_ice_iteration함수를 통해 water큐 에 담긴 좌표를 BFS하며 n_water에 얼음이 녹은 위치를 담고 water에 대입(water = n_water)시켜 물이 얼음을 녹인 진척도를 업데이트한다.

---

Code

from collections import deque
import sys


def find_swan(lake, visited, queue):
    n_queue = deque()
    while queue:
        y, x = queue.popleft()
        if y == swan[1][0] and x == swan[1][1]:
            return True, None
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if not 0 <= ny < R or not 0 <= nx < C or visited[ny][nx]:  """ 인덱스 에러거나 이미 방문했을때 밑에 식 처리안하게"""
                continue
            if lake[ny][nx] == 'X':
                n_queue.append((ny, nx))
            else:
                queue.append((ny, nx))
            visited[ny][nx] = True
    return False, n_queue


def melt_ice_iteration(water, lake):
    n_water = deque()
    while water:
        y, x = water.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if not 0 <= ny < R or not 0 <= nx < C:
                continue
            if lake[ny][nx] == 'X':
                n_water.append((ny, nx))
                lake[ny][nx] = '.'
    return n_water


input = sys.stdin.readline
R, C = map(int, input().split())

lake = []
swan = []
water = deque()
iteration_count = -1
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

for r in range(R):
    one_line = list(input().rstrip())
    for c, value in enumerate(one_line):
        if value == '.' or value == 'L':
            water.append((r, c))
        if value == 'L':
            swan.append((r, c))
    lake.append(one_line)

visited = [[False for _ in range(C)] for _ in range(R)]
queue = deque()

y, x = swan[0][0], swan[0][1]
queue.append((y, x))
visited[y][x] = True

while True:
    iteration_count += 1
    meet, next_q = find_swan(lake, visited, queue)
    if meet:
        break
    water = melt_ice_iteration(water, lake)
    queue = next_q
print(iteration_count)