백준 3055. 탈출

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

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

r, c = map(int, input().split())  # 세로 r, 가로 c
arr = [list(input().strip()) for _ in range(r)]

# 방향 벡터
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

# 방문 배열
visited = [[0] * c for _ in range(r)]

# 큐 선언
water = deque()  # 물의 이동 큐
hedgehog = deque()  # 고슴도치의 이동 큐

# 초기 상태에서 물과 고슴도치의 위치 저장
for i in range(r):
    for j in range(c):
        if arr[i][j] == '*':  # 물
            water.append((i, j))
        elif arr[i][j] == 'S':  # 고슴도치
            hedgehog.append((i, j))
            visited[i][j] = 1  # 고슴도치 방문 처리

# BFS 함수
def bfs():
    while hedgehog:
        # 1. 물의 확장
        for _ in range(len(water)):
            wi, wj = water.popleft()
            for di, dj in directions:
                ni, nj = wi + di, wj + dj
                if 0 <= ni < r and 0 <= nj < c and arr[ni][nj] == '.':
                    arr[ni][nj] = '*'  # 물 확장
                    water.append((ni, nj))

        # 2. 고슴도치 이동
        for _ in range(len(hedgehog)):
            hi, hj = hedgehog.popleft()
            for di, dj in directions:
                ni, nj = hi + di, hj + dj
                if 0 <= ni < r and 0 <= nj < c:
                    if arr[ni][nj] == 'D':  # 비버의 굴 도착
                        return visited[hi][hj]
                    if arr[ni][nj] == '.' and not visited[ni][nj]:  # 빈 칸으로 이동
                        visited[ni][nj] = visited[hi][hj] + 1
                        hedgehog.append((ni, nj))

    return "KAKTUS"

# 결과 출력
print(bfs())