[ 3055 ] [ BFS ] 탈출

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

3055번: 탈출

---

풀이 과정

---

1. 고슴도치와 물의 위치를 저장해 둔다.
2. 단계를 두개로 나누어서 진행한다. 고슴도치가 다음 시간에 물이 찰 예정인 칸으로는 이동할 수 없으므로, 물을 먼저 확산시킨 다음 고슴도치를 이동하는 단계를 거친다.
   1. 물이 퍼지는 단계
   2. 고슴도치가 이동하는 단계
3. BFS 코드를 작성하는데, 고슴도치가 이동하는 횟수를 저장하고, 횟수가 변경될때마다 물을 한번씩 확산시키는 과정을 거친다. 이 때, 물을 확산시키고 나서 확산시킨 위치는 따로 가지고 있어야 다음에 물을 확산시킬 때 위치를 찾을필요 없이 바로 확산시킬 수 있다.
4. 고슴도치가 비버의 굴에 도착하게 되면, 이동시킨 횟수를 출력시켜준다. 도착하지 못하게 되면(큐가 비게되면) KAKTUS를 출력시켜 준다.

---

소스 코드

---

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()
R, C = map(int, input().split())
matrix = [list(input()) for _ in range(R)]

water_pos = deque()
visited_biber = set()
biber = deque()
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

for i in range(R):
    for j in range(C):
        if matrix[i][j] == '*':
            water_pos.append([i, j])
        if matrix[i][j] == 'S':
            visited_biber.add((i, j))
            biber.append([i, j, 0])
            
def flood():
    global R, C, water_pos
    next_deque = deque()
    while water_pos:
        x, y = water_pos.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < R and 0 <= ny and ny < C and \
               matrix[nx][ny] not in ['X', 'D', '*']:
                next_deque.append([nx, ny])
                matrix[nx][ny] = '*'
    water_pos = next_deque

step = -1
while biber:
    x, y, current_step = biber.popleft()
    if matrix[x][y] == '*':
        continue
    if matrix[x][y] == 'D':
        print(current_step)
        break
    
    if current_step != step:
        step = current_step
        flood()

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx and nx < R and 0 <= ny and ny < C:
            if matrix[nx][ny] != '*' and matrix[nx][ny] != 'X' and \
               (nx, ny) not in visited_biber:
                visited_biber.add((nx, ny))
                biber.append([nx, ny, current_step+1])
else:
    print('KAKTUS')