[python] 백준 3055 탈출

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

3055번: 탈출

 

문제 해결

• BFS를 이용하여 푸는 문제라는 것은 쉽게 알 수 있다.
• 문제는 물과 고슴도치가 동시에 이동한다는 것이다.
• 그러나 운이 좋게 문제를 잘 보면 물이 올 지역에 고슴도치가 이동할 수 없다고 나오므로 물부터 이동시킨 후 고슴도치를 이동시키면 된다.
• 고슴도치가 더이상 움직이지 못하면 탈출하지 못하는 것이고 그전에 탈출구를 찾으면 탈출하는데 걸리는 시간을 출력하면 된다.

 

CODE

import sys
input = sys.stdin.readline
from collections import deque

R, C = map(int, input().split())
board = []
dx = [-1,1,0,0]
dy = [0,0,-1,1]
pque = deque() # person deque
wque = deque() # water deque
for i in range(R):
    X = [str(c) for c in input().rstrip()]
    for j in range(C):
        if X[j] == '*':
            wx, wy = i,j
            wque.append((wx,wy))
        if X[j] == 'S':
            sx, sy = i,j
            pque.append((sx,sy))
        if X[j] =='D':
            ex, ey = i,j
    board.append(X)
if sx==ex and sy==ey:
    print(0)
else:
    ans = 1
    while len(pque) !=0:
        twque = deque()
        for i in range(len(wque)):
            wnx, wny = wque[i]
            for j in range(4):
                nwx = wnx + dx[j]
                nwy = wny + dy[j]
                if 0<=nwx<R and 0<=nwy<C and board[nwx][nwy] != 'D' and board[nwx][nwy] != 'X' and board[nwx][nwy] != '*':
                    board[nwx][nwy] = '*'
                    twque.append((nwx,nwy))
        wque = twque
        tpque = deque()
        for i in range(len(pque)):
            pnx, pny = pque[i]
            for j in range(4):
                pwx = pnx + dx[j]
                pwy = pny + dy[j]
                if 0<=pwx<R and 0<=pwy<C and board[pwx][pwy] == 'D':
                    print(ans)
                    exit()
                if 0<=pwx<R and 0<=pwy<C and board[pwx][pwy] == '.':
                    board[pwx][pwy] ='S'
                    tpque.append((pwx,pwy))
        pque = tpque
        ans += 1          
    else:
        print("KAKTUS")