[백준] 3055 탈출 python

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

3055번: 탈출

from collections import deque
import sys; input = sys.stdin.readline
def bfs_step(start_array, visited, opposit_visited, isSonic):
    delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    ret = deque()
    while start_array:
        cur_x, cur_y = start_array.popleft()
        for x, y in delta:
            dx = cur_x + x
            dy = cur_y + y
            if visited[dx][dy] != -1: continue
            if _map[dx][dy] == 'X': continue
            if isSonic and opposit_visited[dx][dy] != -1: continue
            if not isSonic and _map[dx][dy] == 'D': continue
            visited[dx][dy] = visited[cur_x][cur_y] + 1
            ret.append((dx, dy))
    return ret
# 1 입력
R, C = map(int, input().split())
_map = [['X' for _ in range(C + 2)] for _ in range(R + 2)]
water_pos = deque()
sonic_pos = deque()
end = None
for i in range(R):
    tmp = list(input())
    for j in range(C):
        _map[i + 1][j + 1] = tmp[j]
        if tmp[j] == 'D':
            end = (i + 1, j + 1)
        elif tmp[j] == 'S':
            sonic_pos.append((i + 1, j + 1))
        elif tmp[j] == '*':
            water_pos.append((i + 1, j + 1))

# 2 반복문
sonic = [[-1 for _ in range(C+2)] for _ in range(R+2)]
water = [[-1 for _ in range(C+2)] for _ in range(R+2)]
sonic[sonic_pos[0][0]][sonic_pos[0][1]] = 0
for x, y in water_pos:
    water[x][y] = 0

while True:
    # 2-1 고슴도치 이동
    tmp_sonic = bfs_step(sonic_pos, sonic, water, True)
    # 2-2 물이동
    tmp_water = bfs_step(water_pos, water, sonic, False)
    # 2-3 도착 불가능
    if not tmp_sonic:
        print('KAKTUS')
        break
    # 2-4 도착 가능
    if sonic[end[0]][end[1]] != -1:
        print(sonic[end[0]][end[1]])
        break
    # 2-5 다음 이동 
    sonic_pos = deque(set(tmp_sonic)-set(tmp_water))
    water_pos = tmp_water

# print("hello, world")

고슴도치와 물의 위치를 각각 받아 너비우선탐색을 한스텝씩 돌렸고, 이동하는 위치를 리턴받아 고슴도치가 갈수 있는지 확인하였다. 너비우선탐색에서 최소거리를 파악해야하므로 방문한지점은 현재 지점보다 1 큰 값으로 저장한다.

고슴도치의 위치에 물이 있는 경우 해당 부분을 빼서 다음 스텝으로 넘겨주고 물은 그대로 다음으로 넘긴다.

계속 반복하여 고슴도치가 'D'에 도착하는 경우 해당 값을 출력하고, 도착하지 못하는 경우 kaktus를 출력한다.

---

어려운 문제는 아닌데 구현이 꽤 걸린 문제였다.