백준 3055 탈출 파이썬 BFS 풀이

물에 빠진 고슴도치

문제가 길고 장황해서 살짝 쫄았지만, 몇 가지 포인트를 고려하니 어렵지 않게 풀리는 문제였다. 

노드간 간격이 일정하고 가장 빠른시간을 묻는 문제이기 때문에 BFS풀이가 적합하다.

 

문제풀이 포인트

• 고슴도치는 물을 피해서 'D'로 도착해야함.
• 고슴도치는 한번에 1칸 이동 / ' . ' 으로만 이동 가능
• 물은 인접한 영역으로 한번에 한칸씩 확장 / 'X', 'D' 일 경우 이동 불가
• 고슴도치는 물이 이동 예정인 곳으로 이동 불가능
  → 큐에 물을 먼저 넣고 그 이후 고슴도치를 넣는다. 

from collections import deque
import sys
input=sys.stdin.readline
R,C=map(int,input().split())
arr=[list(input().strip()) for _ in range(R)]
dx=[1,-1,0,0]
dy=[0,0,1,-1]

def escape():
    queue=deque()
    for i in range(R):
        for j in range(C):
            if arr[i][j]=='D':   #도착지 좌표기록 후 루프 탈출 조건에 사용
                D=[i,j]                
            elif arr[i][j]=='*':    #물 위치 기록 후 큐에 먼저 넣는다.
                queue.append([i,j,'*'])
            elif arr[i][j]=='S':
                arr[i][j]==1
                S=[i,j,0]       
    queue.append(S)            #물이 모두 큐에 들어간 이후에 고슴도치를 넣는다.
  
    while queue:
        x,y,z=queue.popleft()
        if x==D[0] and y==D[1]:
            print(z)
            break
        else:
            for i in range(4):  #물과 고슴도치의 인접영역으로 이동 가능 여부 확인 후 이동
                nx=x+dx[i]
                ny=y+dy[i]
                if z=='*' and 0<=nx<R and 0<=ny<C and arr[nx][ny]!='X' and arr[nx][ny]!='D' and arr[nx][ny]!='*':
                    arr[nx][ny]='*'
                    queue.append([nx,ny,'*'])
                elif type(z)==int and 0<=nx<R and 0<=ny<C and (arr[nx][ny]=='.' or arr[nx][ny]=='D'):
                    arr[nx][ny]=z+1
                    queue.append([nx,ny,z+1])
        if len(queue)==0:
            print('KAKTUS')
            break     

escape()