BOJ - 9376 - 탈옥

import sys
from collections import deque

def BFS(W, H, maps, x, y):
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]

    person = deque()
    person.append((x, y))

    dist = [[-1 for _ in range(W)] for _ in range(H)]
    dist[x][y] = 0

    while person:
        x, y = person.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < H and 0 <= ny < W:

                if dist[nx][ny] >= 0 or maps[nx][ny] == '*': 
                    continue

                if maps[nx][ny] == ".":
                    dist[nx][ny] = dist[x][y]
                    person.appendleft((nx, ny))
                    
                elif maps[nx][ny] == "#":
                    dist[nx][ny] = dist[x][y] + 1
                    person.append((nx, ny))

    return dist

def solution():
    T = int(input())
    for _ in range(T):
        maps = []
        person = deque()
        H, W = map(int, sys.stdin.readline().split())

        maps.append(list('.' * (W + 2)))
        for _ in range(H):
            maps.append(list(str('.'+sys.stdin.readline().strip()+'.')))
        maps.append(list('.' * (W + 2)))

        for i in range(H+2):
            for j in range(W+2):
                if maps[i][j] == "$":
                    maps[i][j] = '.'
                    person.append((i, j))

        x, y = person.pop()
        newMap1 = BFS(W + 2, H + 2, maps, x, y)
        x, y = person.pop()
        newMap2 = BFS(W + 2, H + 2, maps, x, y)
        newMap3 = BFS(W + 2, H + 2, maps, 0, 0)

        answer = 1e9
        for i in range(H + 2):
            for j in range(W + 2):
                if maps[i][j] == '*': continue
                val = newMap1[i][j] + newMap2[i][j] + newMap3[i][j]

                if maps[i][j] == '#': val -= 2

                answer = min(answer, abs(val))

        print(answer)

solution()

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