BOJ - 3055 - 탈출

import sys
from collections import deque

def BFS(dq, Map, N, M):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    Q = deque()
    while dq:
        x, y = dq.pop()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < M:
                if Map[x][y] == '*':
                    if Map[nx][ny] == "." or Map[nx][ny] == "S":
                        Map[nx][ny] = "*"
                        Q.append((nx, ny))
                elif Map[x][y] == "S":
                    if Map[nx][ny] == ".":
                        Map[nx][ny] = "S"
                        Q.append((nx, ny))

                    elif Map[nx][ny] == "D":
                        return True
    return Q

def solution():
    R, C = map(int, sys.stdin.readline().split())
    Map = []
    start = deque()
    water = deque()

    for _ in range(R):
        Map.append(list(str(sys.stdin.readline().strip())))

    for i in range(R):
        for j in range(C):
            if Map[i][j] == 'S':
                start.append((i, j))
            elif Map[i][j] == 'D':
                end = [(i, j)]
            elif Map[i][j] == '*':
                water.append((i, j))

    time = 0
    while True:
        time += 1
        start = BFS(start, Map, R, C)
        water = BFS(water, Map, R, C)

        if start == True:
            print(time)
            break
        elif not start:
            print("KAKTUS")
            break

        temp = []
        for x, y in start:
            if Map[x][y] == 'S':
                temp.append((x, y))
        start = temp

solution()

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