[백준][Python]3055번(탈출)

백준 3055번

✔️ 문제 풀이

◾ 물의 경로를 탐색한 배열 활용

• 고슴도치를 움직이기 전에 물의 경로를 먼저 탐색한다
• bfs를 활용하여 방문하면서 몇 초에 어느 공간이 물에 젓는지를 배열에 저장한다
  (물의 시작점과 각 공간까지의 최소 거리를 구하는 논리)
• 고슴도치를 bfs를 통해 움직이며 방문하려는 위치가
  1) 방문한 적이 없으며
  2) 돌이 없고
  3) 현 시간에 물에 젓지 않은 곳
  이라면 큐에 현 위치와 지금까지 경과한 시간을 넣어준다.
• 큐가 빌때까지 result 값이 갱신되지 않으면 비버의 집에 접근할 수 없는 것

최종 제출 코드

import sys
import copy
from collections import deque
input = sys.stdin.readline

R, C = map(int, input().split())
roadmap = []
start = []
water = deque()
watered = [[-1]*C for _ in range(R)]
visited = [[False]*C for _ in range(R)]

for i in range(R):
  row = input()
  for j in range(C):
    if row[j] == 'S':
      start.append((j, i))
    elif row[j] == '*':
      water.append((j, i, 0))
  roadmap.append(row)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def watering():

  for x, y, times in water:
    watered[y][x] = 0

  while water:
    
    x, y, times = water.popleft()

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

      if nx < 0 or ny < 0 or nx >= C or ny >= R:
        continue
      if watered[ny][nx] == -1 and roadmap[ny][nx] == '.':
        watered[ny][nx] = times+1
        water.append((nx, ny, times+1))

watering()


q = deque()
x, y = start.pop()
q.append((x, y, 0))
visited[y][x] = True

result = 0

while q:

  x, y, times = q.popleft()

  if roadmap[y][x] == 'D':
    result = times
    break

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

    if nx < 0 or ny < 0 or nx >= C or ny >= R:
      continue
    
    if roadmap[ny][nx] != 'X' and not visited[ny][nx] and (watered[ny][nx] == -1 or watered[ny][nx] > times+1):
      visited[ny][nx] = True
      q.append((nx, ny, times+1))

print(result if result else "KAKTUS")

✔️ 실행 결과