백준 9376번: 탈옥 (Python)

접근

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

9376번: 탈옥

처음에는 DFS로 풀고 예시를 맞춘다음 이것을 최적화해보려했지만, 딱봐도 계산이 많아서 어려울 것이라고 생각하고 다른 방법이 떠오르지 않아 다른 블로그의 글을 여러개 참고하여 풀 수 있었다. 설명을 봐도 이해하기가 어려웠던 문제였다. 정리차원에서 말하자면 풀이를 위한 총 3가지의 핵심 개념이 있었다.

1. 각 죄수들을 시작점으로 하는 BFS 를 진행하여 해당 죄수가 특정 위치 (r, c)에 도달했을 때 그 위치까지 문을 몇 개 열고왔는지 탐색한다. 이 과정에서 0 1 BFS 방법을 이용하여 가중치가 낮은 (문을 덜 여는) 길을 queue의 맨 앞에 추가하여 문을 많이 여는 경로가 저장되지 않도록 한다. 이 방법을 쓰지 않고 그냥 BFS로 탐색한다면, 칸수로는 작지만 문을 많이 여는 길과 칸수가 많지만 문을 적게 여는 길이 한 지점에서 만날 때, 문을 많이 여는 길이 먼저 교차로에 도달하여 해당 칸을 저장해버리게 된다.
2. 상근이는 감옥의 밖에서 출발한다. 감옥 밖에서는 자유롭게 이동할 수 있기 때문에 감옥 밖에서 이동할 때 문여는 갯수가 0인 통로를 지난다고도 볼 수 있다. 이를 쉽게 계산하기 위해 주어진 감옥 지도의 맨 바깥쪽에 값이 '.'인 통로를 주욱 둘러준다. 또한 감옥 외부의 위치에서 시작하는 0 1 BFS를 진행해준다.
3. 위에서 구해진 죄수1, 죄수2, 감옥밖 에서 시작하는 0 1 BFS의 결과물을 모두 합치면, 감옥밖에서 온 상근이, 죄수1, 죄수2가 (r, c)에서 만났을 때 각자의 위치에서 문을 몇개 열고 왔는지의 값을 의미하게 된다. (해당 위치에 문이 존재한다면 중복을 제거하기 위해 -2를 해준다.) 즉 세 번의 0 1 BFS의 결과물들의 값을 모두 더한 값 중 가장 작은 값이 정답이 된다.

문제를 이해하기도 어렵고 설명하기도 어려운 문제였다.

코드

import sys
from collections import deque

input = sys.stdin.readline

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]


# (r, c)에서 시작하여 진행하면서 해당 위치에 도달하기 까지 문을 연 갯수를 해당 칸에 표시
def bfs(r, c):
    visited = [[-1] * (C + 2) for _ in range(R + 2)]
    queue = deque()
    queue.append((r, c))
    visited[r][c] = 0
    while queue:
        r, c = queue.popleft()
        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]
            if nr < 0 or R + 2 <= nr or nc < 0 or C + 2 <= nc or visited[nr][nc] != -1:
                continue
            if matrix[nr][nc] == ".":
                # 문을 열지 않았다면 appendleft 해줌으로써 가중치가 작은(문을 덜 여는) 경로가 우선적으로 탐색될 수 있도록 함
                visited[nr][nc] = visited[r][c]
                queue.appendleft((nr, nc))
            elif matrix[nr][nc] == "#":
                # 문을 열었다면 문 연 갯수를 1 더해주고 큐의 맨 뒤로 추가
                visited[nr][nc] = visited[r][c] + 1
                queue.append((nr, nc))
    return visited


T = int(input())
for _ in range(T):
    R, C = map(int, input().split())
    matrix = ["." * (C + 2)]
    for _ in range(R):
        matrix.append(["."] + list(input().strip()) + ["."])
    matrix.append(["."] * (C + 2))
    prisoner = []
    for i in range(R + 2):
        for j in range(C + 2):
            if matrix[i][j] == "$":
                prisoner.append([i, j])
                matrix[i][j] = "."

    cnt1 = bfs(prisoner[0][0], prisoner[0][1])
    cnt2 = bfs(prisoner[1][0], prisoner[1][1])
    cnt3 = bfs(0, 0)

    ans = float("inf")
    for i in range(1, R + 1):
        for j in range(1, C + 1):
            if cnt1[i][j] == -1 or cnt2[i][j] == -1 or cnt3[i][j] == -1:
                continue
            if matrix[i][j] == ".":
                ans = min(ans, cnt1[i][j] + cnt2[i][j] + cnt3[i][j])
            elif matrix[i][j] == "#":
                ans = min(ans, cnt1[i][j] + cnt2[i][j] + cnt3[i][j] - 2)
    print(ans)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!