# BOJ - 9376 - 탈옥

Updated:

``````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()

maps.append(list('.' * (W + 2)))
for _ in range(H):
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)

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