BOJ 3055 탈출

https://www.acmicpc.net/problem/3055
시간 1초, 메모리 128MB
input :

• R C (1 <= R, C <= 50)
• R개의 줄에 지도가 주어짐.
• 'D'와 'S'는 1개씩만 주어짐.

output :

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

조건 :

• 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.
• 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다.
• 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동
• 물과 고슴도치는 돌을 통과할 수 없다.
• 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

일단, 물이 매 분마다 비어있는 칸으로 확장하기 때문에 비버가 이동하기 전에 물이 먼저 확장 되어야 한다.
비버가 이동을 하는 경우네는 빈 공간인지 확인, 도착지점인지 확인 해야 한다.

이렇게 while문을 통해 물 확장, 비버 이동. 을 계속 수행하게 한다.
이 때, 비버가 이동 하다 도착지점에 왔는지를 확인 하기 위한 변수를 하나 두어야 한다.

물을 확장 시킬 때, 현재 까지의 물이 존재하는 지점들을 큐에 저장해서 이 길이 만큼 BFS가 수행 되도록 한다. 그 이상의 경우는 시간이 더 지난 경우이기 때문에 재낀다.
고슴도치가 이동하는 방법도 위와 동일하게 하도록 한다.

더 이상 고슴도치가 이동할 공간이 없다면 while문을 빠져나오게 해서 "KAKTUS"를 출력하게 한다. 비버 굴로 들어갔으면 while문을 돌다가 if문에서 exit(0)를 만나 탈출했을 것이다.

import sys
from collections import deque

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def water():
    times = len(obstacle)
    for i in range(times):
        x, y = obstacle.popleft()

        for j in range(4):
            next_x = x + dx[j]
            next_y = y + dy[j]

            if next_x < 0 or next_x >= r or next_y < 0 or next_y  >= c:
                continue

            if data[next_x][next_y] == ".":
                data[next_x][next_y] = "*"
                obstacle.append((next_x, next_y))

def bfs():
    times = len(q)

    for i in range(times):
        now_x, now_y = q.popleft()

        for j in range(4):
            next_x = now_x + dx[j]
            next_y = now_y + dy[j]

            if next_x < 0 or next_x >= r or next_y < 0 or next_y >= c:
                continue

            if data[next_x][next_y] == ".":
                data[next_x][next_y] = "S"
                q.append((next_x, next_y))

            if data[next_x][next_y] == "D":
                return 1;
    return 0;

r, c = map(int, sys.stdin.readline().split())
data = []

obstacle = deque()
q = deque()
for i in range(r):
    temp = list(sys.stdin.readline().strip())

    for idx, item in enumerate(temp):
        if item == "S":
            q.append((i, idx))
        elif item == "*":
            obstacle.append((i, idx))

    data.append(temp)

cnt = 0
while q:
    cnt += 1
    water()
    ret = bfs()

    if ret == 1:
        print(cnt)
        exit(0)

print("KAKTUS")