[Python] 백준 3055 탈출

1. 문제 - 백준 3055 탈출

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

 

💡알고리즘 - BFS

• 인접한 칸으로 이동하며, 고슴도치가 비버의 굴로 이동하기 까지의 최소 시간을 구하는 문제이므로 BFS를 활용한다.
• 일반 BFS와 다른 점은 고슴도치가 단순히 탐색하는 것이 아니라 아래 사항을 고려해야한다.
  1) 물도 같이 인접한 칸으로 흐름
  2) 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 

✅ 풀이

• 물과 고슴도치가 동시에 인접한 칸으로 움직인다.
• 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다.

=> 물이 인접한 칸으로 차는 최소 시간을 먼저 기록한뒤 (visited_w)
고슴도치가 그 다음 방문할 예정인 칸에 도달했을 때의 최소 시간 (visited) 과 비교하며 이동한다.

 

from collections import deque

r, c = map(int, input().split())
board = []
dx = [-1, 1, 0, 0]    # 인접한 칸으로 이동하기 위한 offset 배열
dy = [0, 0, -1, 1]
start_x, start_y = 0, 0   # 고슴도치가 이동을 시작하는 변수 (처음 고슴도치 위치)
end_x, end_y = 0, 0       # 고슴도치가 도착하는 변수 (굴의 위치)

water_q = deque([])     # 물의 위치를 저장하기 위한 Q (이후에 BFS를 통해 물이 인접한 칸으로 흐르는 최소 시간을 기록할 것이므로 q에 만들어서 저장한다.)

for i in range(r):
  board.append(list(input()))
  for j in range(c):
    if board[i][j] == "D":     # 굴의 위치 -> end
      end_x, end_y = i, j
    elif board[i][j] == "S":   # 고슴도치의 위치 -> start
      start_x, start_y = i, j
    elif board[i][j] == "*":   # 물의 위치
      water_q.append((i, j))

visited_w = [[-1] * c for _ in range(r)]
visited = [[-1] * c for _ in range(r)]

# 물이 차는 최소 시간 구하기 (visited_w)
for x, y in water_q:
  visited_w[x][y] = 0

while water_q:
  x, y = water_q.popleft()

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

    # 물은 돌이나 비버의 소굴로 이동할 수 없다. 즉 빈칸(.) 일때만 이동한다.
    if 0<=nx<r and 0<=ny<c and visited_w[nx][ny] == -1 and board[nx][ny] == ".":
      visited_w[nx][ny] = visited_w[x][y] + 1
      water_q.append((nx, ny))

# 비버가 굴까지 이동하는 최소 시간 구하기 (visited)
q = deque([(start_x, start_y)])
visited[start_x][start_y] = 0

while q:
  x, y = q.popleft()

  if x == end_x and y == end_y:
    print(visited[x][y])
    exit()

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

    # 비버는 돌이 아니면 다 이동할 수 있고 (board[nx][ny] != "X"),
    # 다음 시간에 물이 찰 예정인 칸으로 이동할 수 없다 (visited[x][y] + 1 < visited_x[nx][ny])
    if 0<=nx<r and 0<=ny<c and board[nx][ny] != 'X' and visited[nx][ny] == -1 and visited[x][y] + 1 < visited_w[nx][ny]:
      q.append((nx, ny))
      visited[nx][ny] = visited[x][y] + 1

print("KAKTUS")     # 비버의 굴로 이동할 수 없다면, KAKTUS 출력