(Python) - BOJ(3055번) : 탈출

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

3055번: 탈출

---

• 해설 : 

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

 

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

 

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

 

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 

 

 

 

---

• 풀이 :

물이 차는 상황과, 고슴도치가 이동할 수 있는 칸을 동시에 bfs로 탐색하며 고슴도치가 갈 수 있는 칸들을 계속 리셋해준다.  완전히 동시에는 아니고 물이 먼저 찬 이후에 고슴도치가 이동할 수 있으므로 물이 차는 경우를 먼저 bfs로 탐색해준다.

 

 

 

---

• 소스코드 : 

 

import sys
 
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs(start):
    b_queue = [[start]]
    w_queue = [drown[-1]]
    i=0
    while b_queue[-1] or w_queue[-1]:
        w_queue.append([])
        for k in w_queue[i]:
            x,y = k
            for z in range(4):
                ax = x + dx[z]
                ay = y + dy[z]
                if 0 <= ax < r and 0 <= ay < c:
                    if maps[ax][ay] == ".":
                        w_queue[-1].append([ax,ay])
                        maps[ax][ay] = "*"
        b_queue.append([])
        for k in b_queue[i]:
            x,y = k
            for z in range(4):
                ax = x + dx[z]
                ay = y + dy[z]
                if 0<= ax < r and 0 <= ay < c:
                    if maps[ax][ay] == "D":
                        print(i+1)
                        return
                    if maps[ax][ay] == ".":
                        b_queue[-1].append([ax,ay])
                        maps[ax][ay] = "S"
        
 
        i+=1
    print("KAKTUS")
 
 
if __name__ == "__main__":
    r,c = map(int,sys.stdin.readline().split())
    maps = []
    for _ in range(r):
        maps.append(list(input()))
    drown = []
    drown.append([])
    for i in range(r):
        for j in range(c):
            if maps[i][j] == "S":
                start = [i,j]
            if maps[i][j] == "*":
                drown[0].append([i,j])
    bfs(start)