[백준] 3055 - 탈출 (Python)

문제

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

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

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

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

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

---

입력

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

출력

첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

---

예제 입력

3 6
D...*.
.X.X..
....S.

예제 출력

6

---

해결 방법

먼저 고슴도치의 위치를 찾아 queue에 넣어준다. 

그 다음 물의 위치들을 찾아 queue에 넣어준다. 

 

위 순서로 queue에 넣어주면 고슴도치가 먼저 이동하고 이후 물이 이동하는 과정을 자동으로 반복할 수 있

 

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

r,c = map(int,input().split())

map = []
queue = deque()
visited = [[0]*c for _ in range(r) ]

direction = [(1,0), (0,1), (-1,0), (0,-1)]
for i in range(r):
    map.append(list(input().rstrip()))

# 고슴도치 위치 찾기
for i in range(r):
    if "S" in map[i]:
        sx,sy = (i, map[i].index("S"))
        queue.append((sx,sy))

# 물 위치 찾기
for i in range(r):
    if "*" in map[i]:
        queue.append((i, map[i].index("*")))

# 비버의 굴 위치
for i in range(r):
    if "D" in map[i]:
        bx,by = (i, map[i].index("D"))
        break

def checkValid(x,y):
    return 0 <= x < r and 0 <= y < c

def bfs(x,y):
    visited[x][y] = 1
    while queue:
        for _ in range(len(queue)):
            cx,cy = queue.popleft()
            
            if map[cx][cy] == 'D':
                break
            
            for dx, dy in direction:
                nx, ny = cx + dx, cy + dy
                if checkValid(nx,ny):
                    if map[cx][cy] == 'S' and (map[nx][ny] == '.' or map[nx][ny] == 'D'):
                        visited[nx][ny] = visited[cx][cy] + 1
                        map[nx][ny] = "S"
                        queue.append((nx,ny))
                    elif map[cx][cy] == '*' and (map[nx][ny] == '.' or map[nx][ny] == 'S'):
                        map[nx][ny] = '*'
                        queue.append((nx,ny))

bfs(sx,sy)
if visited[bx][by]:
    print(visited[bx][by] - 1)
else:
    print("KAKTUS")