[ 9376 ] [ BFS ] 탈옥

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

9376번: 탈옥

그냥 풀기 너무 어려워서 백준 내 질문게시판을 참조함..

풀이 과정

---

1. 출구가 한곳이 아니므로 전체 테두리를 .으로 감싸서 외부에서 시작할 때는 [0, 0]에서 시작할 수 있도록 한다.
2. 총 3번의 BFS를 진행하여야 한다.
   1. 1번 죄수 기준으로 BFS를 진행하여 전체 지점에서 부숴야 하는 최소 벽 개수를 구한다.
   2. 2번 죄수 기준으로 BFS를 진행하여 전체 지점에서 부숴야 하는 최소 벽 개수를 구한다.
   3. 외부 조력자 기준([0, 0])으로 BFS를 진행하여 전체 지점에서 부숴야 하는 최소 벽 개수를 구한다.
3. 전체 좌표에 대해서, 1번 죄수가 부숴야하는 벽, 2번 죄수가 부숴야하는 벽, 외부 조력자가 부숴야 하는 벽의 수를 모두 합한 값이 최소일 때의 값을 출력한다.
   • 단, 이 때 현 좌표가 벽인 경우는 1~3번이 모두 부수므로 2를 빼준다.

---

소스 코드

---

 

import sys
from collections import deque as Deque

input = lambda: sys.stdin.readline().rstrip()
T = int(input())

def bfs(matrix, x, y):
    new_matrix = [[int(10e9)] * len(matrix[0]) for _ in range(len(matrix))]
    deque = Deque([[x, y]])
    dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]
    R, C = len(matrix), len(matrix[0])
    visited = [[False] * C for _ in range(R)]
    visited[x][y] = True
    new_matrix[x][y] = 0
    while deque:
        cx, cy = deque.popleft()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= nx and nx < R and 0 <= ny and ny < C:
                if not visited[nx][ny] and matrix[nx][ny] == '.':
                    new_matrix[nx][ny] = new_matrix[cx][cy]
                    deque.appendleft([nx, ny])
                elif not visited[nx][ny] and matrix[nx][ny] == '#':
                    new_matrix[nx][ny] = new_matrix[cx][cy]+1
                    deque.append([nx, ny])
                visited[nx][ny] = True
    return new_matrix

for _ in range(T):
    h, w = map(int, input().split())
    matrix = [list('.'+input()+'.') for _ in range(h)]
    matrix = [['.'] * (w+2)] + matrix + [['.'] * (w+2)]
    player = []
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == '$':
                player.append([i, j])
                matrix[i][j] = '.'
                
    playerA, playerB = player[0], player[1]
    matrix1 = bfs(matrix, 0, 0)
    matrix2 = bfs(matrix, playerA[0], playerA[1])
    matrix3 = bfs(matrix, playerB[0], playerB[1])

    answer = int(10e9)
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == '*':
                continue
            sumation = matrix1[i][j] + matrix2[i][j] + matrix3[i][j]
            if matrix[i][j] == '#':
                answer = min(answer, sumation-2)
            else:
                answer = min(answer, sumation)

    print(answer)