[백준✨] 3055번 <탈출> / Python 문제풀이 / BFS

해답)

from collections import deque
import sys

'''
@@@ 입력받기 @@@
'''

def input():
  return sys.stdin.readline().rstrip()

R, C = map(int, input().split())

board = []
visited = [[False for _ in range(C)] for _ in range(R)]

for _ in range(R):
  board.append(list(input()))
  
cnt = 0
success = False
q = deque([])
dir =[(-1,0),(1,0),(0,1),(0,-1)]

'''
@@@ 큐에 현재 물과 고슴도치를 넣어준다. @@@
 - 반드시 물부터 넣어주어야함
'''
for r in range(R):
  for c in range(C):
    if board[r][c] == "*": # 물
      q.append(("*", 0, r,c))
      
for r in range(R):
  for c in range(C):
    if board[r][c] == "S": # 고슴도치
      q.append(("S", 0, r, c))
      visited[r][c] = True
      
while q:
  what, cnt, now_r, now_c = q.popleft()
  for _r, _c in dir:
    nxt_r, nxt_c = now_r + _r, now_c + _c
    if not (0<=nxt_r<R) or not (0<=nxt_c<C):
      continue
    if what == "*": # 물
      if board[nxt_r][nxt_c] == ".":
        board[nxt_r][nxt_c] = "*" # 범람시키기
        q.append((what, cnt+1, nxt_r, nxt_c))
    else:
      if visited[nxt_r][nxt_c]:
        continue
      if board[nxt_r][nxt_c] == ".": # 고슴도치
        q.append((what, cnt+1, nxt_r, nxt_c))
        visited[nxt_r][nxt_c] = True
      elif board[nxt_r][nxt_c] == "D": # 굴 도착
        success = True
        break
  if success:
    break

if success:
  print(cnt+1) # 도착전 cnt 의 + 1 
else:
  print("KAKTUS")

 

---

풀이)

문제를 자세히 읽고, BFS로 그대로 구현하기만 하면 되는 문제입니다.

 

몇 가지 포인트를 집어보자면

1. 물이 먼저 이동해야된다. ( 물 부터 큐에 집어넣고, 고슴도치 위치를 큐에 집어넣어야합니다. )

2. 고슴도치 위치는 visited 판단을 시킨다. ( 고슴도치가 갔던데를 또 가는 쓸데없는 경우를 제외시켜줍니다. )

  

 

 

 

 

* 위 문제의 저작권은 백준(https://www.acmicpc.net/) 에 있습니다.