백준 9376번 탈옥 (Python 3)

Baekjoon online judge 9376번 파이썬

 

링크

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

9376번: 탈옥

생각보다 어려웠다.

처음에는 각 죄수들에 대해서 0-1 bfs를 돌려서 둘의 최소 문을 부순 횟수를 더해 주면 될거라고 생각했는데,

이렇게 하면 죄수 1의 최소경로가 전체의 최소경로가 아닌 경우는 올바른 답이 나오지 않는다.

감옥 밖, 죄수1 죄수 2에 대해서 0-1 bfs를 수행한다. 

감옥 밖으로 이어져 있는 경로 + 죄수 1과 이어져 있는 경로 + 죄수 2와 이어져 있는 경로

(visited== -1)

인 경우일 때 최소 값을 찾는다. 이때 문 (#) 인 경우에는 3명이 같은 문을 3번 부쉈기 때문에 cnt에서 2를 빼준다.

 

소스코드

import sys
from collections import deque
input = sys.stdin.readline
index=[[1,0],[-1,0],[0,1],[0,-1]]

def bfs(x,y):
  queue=deque()
  visited=[[-1 for _ in range(w+2)] for _ in range(h+2)]
  queue.append([y,x])

  visited[y][x]=0

  while queue:
    qy,qx=queue.popleft()

    for indy,indx in index:
      ny=indy+qy
      nx=indx+qx

      if 0<=nx<w+2 and 0<=ny<h+2 and visited[ny][nx]==-1:
        if map_data[ny][nx]=='.':
          visited[ny][nx]=visited[qy][qx]
          queue.appendleft([ny,nx])

        elif map_data[ny][nx]=='#':
          visited[ny][nx]=visited[qy][qx]+1
          queue.append([ny,nx])

  return visited

for _ in range(int(input())):

  h, w = map(int, input().split())
  map_data=[['.' for _ in range(w+2)]]
  for __ in range(h):
    map_data.append(list('.'+input().rstrip()+'.'))
  map_data.append(['.' for _ in range(w+2)])

  prison=list()

  for i in range(h+2):
    for j in range(w+2):
      if map_data[i][j]=='$':
        prison.append([i,j])
        map_data[i][j]='.'

  ey,ex=prison[1]
  sy, sx = prison[0]

  ans1=bfs(0,0)
  ans2=bfs(sx,sy)
  ans3=bfs(ex,ey)

  now_min=sys.maxsize

  for i in range(h+2):
    for j in range(w+2):
      if ans1[i][j]!=-1 and ans2[i][j]!=-1 and ans3[i][j]!=-1:
        cnt=ans1[i][j]+ans2[i][j]+ans3[i][j]

        if map_data[i][j]=='#':
          cnt-=2
        now_min=min(now_min,cnt)

  print(now_min)