3055. 탈출

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

✔ 유형 : BFS

✔ 문제 풀이: 시간당 고슴도치의 위치와, 시간당 물의 위치를 매 주기마다 업데이트 하고, 물도착시간이 고슴도치의 도착시간보다 느릴 때 고슴도치가 이동 가능함을 이용해 문제를 해결한다. 최소한으로 도착했을 때의 시간을 알아야 하기 떄문에 BFS를 사용한다.

 

코드

import sys
from collections import deque
input=sys.stdin.readline # input함수 바꾸기

# 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'
# 비버의 굴 = D
# 귀여운 고슴도치 = S
# 매 분기 도치는 4방향중 한칸 이동가능. 물은 매분마다 비어있는 곳으로 확장. 한변을 공유하는 곳이면!
# 물과 고슴도치는 돌 통과 노노링
# 물은 비버소굴 못가고, 비버는 물로 모못감.
# 도슴도치가 비버굴로 가기위한 최소 시간은? 누가봐도 BFS 죠?

# 입력
R, C = map(int, input().split())
Map = [list(input().rstrip()) for _ in range(R)] # 붙여서 입력받기 rstrip!!!

# 매 분마다 물과 고슴도치가 이동한다. 물이 먼저 차고 고슴도치가 이동해야함니다.
dx = [1,-1,0,0]
dy = [0,0,1,-1]

dochi_queue = deque()
water_queue = deque()
visited =[[-1 for _ in range(C)] for _ in range(R)] # 최소시간 = 최소거리
water_visited =[[-1 for _ in range(C)] for _ in range(R)] # 최소시간 = 최소거리


def BFS():
    # waterqueue는 물의 위치를 가진 큐이고 4방향으로 이동한다.
    # x,y는 도치의 위치.
    # 물이 퍼져나가면서 Map에 반영되어야 함.
    
    # 도치씨가 비버네집에 도착할 떄 까지
    # 물이랑 도치가 시간단위로 이동이 같으니, 물도 distance 배열을 만들어서 시간 비교를 통해 도치가갈수있는지 판단할 수 있따.
    # 1. 물이 먼저 이동함.
    while water_queue:
        #물의 위치
        wx, wy = water_queue.popleft() 

        for d in range(4):
            nwx = wx + dx[d]
            nwy = wy + dy[d]
            # 인덱스 범위 확인
            if 0 <= nwx < R and 0 <= nwy < C and Map[nwx][nwy] == '.'and water_visited[nwx][nwy] == -1: # 물이 아직 안간 곳이라면
                water_visited[nwx][nwy] = water_visited[wx][wy] + 1 # 도착 시간 갱신
                water_queue.append((nwx, nwy))

                
                
    while dochi_queue:
        #도치의 위치
        x ,y = dochi_queue.popleft()   
        
        for k in range(4): 
            nx = dx[k] + x
            ny = dy[k] + y
            if nx < 0 or ny < 0 or nx >= R or ny >= C : continue
            if Map[nx][ny] == 'D': #굴에 도착?
                return str(visited[x][y]+1)
            if Map[nx][ny] == '.'and visited[nx][ny] == -1: #갈 수있는 곳이고 도치가간적이 없을 때
                if visited[x][y]+1 < water_visited[nx][ny] or water_visited[nx][ny] == -1:
                    # 현재 도치의 시간 +1 했을때 물이 오는 시간보다 작은지 확인!
                    visited[nx][ny] = visited[x][y] + 1
                    
                    dochi_queue.append((nx,ny)) #도치의 새로운 이동 추가~
                   
            
                
            
     
    return "KAKTUS"
        

# 고슴도치가 있는 위치와 물이 차있는 위치를 큐에 저장. 
for i in range(0,R):
    for j in range(0,C):
        if Map[i][j] == 'S':
            dochi_queue.append((i,j))
            visited[i][j] = 0 # 도치의 위치는 방문처리 0으로 둔다.시작점이니까.
        elif Map[i][j] == "*":
            water_queue.append((i,j))
            water_visited[i][j] = 0

            
            
print(BFS())