[Python] BOJ / 3055번 / 탈출

3055번: 탈출

---

📝 풀이

• 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다.
  • 물이 차 있는 곳 먼저 각각 큐에 저장하고 BFS를 수행하기 직전에 고슴도치의 위치를 큐에 저장함으로써 물이 먼저 확장되고 나서 고슴도치가 이동하는 식으로 구현
• 큐에는 (y좌표, x좌표, 타입, 시간) 값이 들어감
  • 타입 값은 현재 이동중인 개체(고슴도치 또는 물)를 나타냄 
  • 시간 값은 현재 좌표까지 이동하는데 걸리는 시간을 나타냄

---

💻 소스코드

import sys
from collections import deque

input = sys.stdin.readline
dy = (1, -1, 0, 0)
dx = (0, 0, 1, -1)

def bfs(start_y, start_x):
    que.append((start_y, start_x, 'S', 0))
    visited[start_y][start_x] = True

    while que:
        y, x, type, time = que.popleft()

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if not 0 <= ny < r or not 0 <= nx < c:
                continue

            if graph[ny][nx] == '.' and not visited[ny][nx]:
                visited[ny][nx] = True
                que.append((ny, nx, type, time + 1))
            elif graph[ny][nx] == 'D' and type == 'S':
                return time + 1

    return "KAKTUS"

r, c = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(r)]
visited = [[False] * c for _ in range(r)]
que = deque()

start_y = start_x = 0
for i in range(r):
    for j in range(c):
        if graph[i][j] == 'S':
            start_y, start_x = i, j
        elif graph[i][j] == '*':
            que.append((i, j, '*', 0))

print(bfs(start_y, start_x))