[BOJ 백준] 9376번 : 탈옥(Python, 파이썬)

www.acmicpc.net/problem/9376

9376번: 탈옥

 

첫 플레문제였다. 단순히 다익스트라나 BFS로 하면 될 것 같았는데 아무리 고민을 해도 시간복잡도를 알맞게 할 수 없을 것 같아서 다른 블로그를 보고 풀었다.

 

찾아보니 이런 유형의 문제는 0-1 BFS라고 한다.

 

가중치가 0과 1만 있는 그래프에서 사용할 수 있는데, 기존의 BFS는 방향탐색을 마치고, 다음에 갈 지점을 큐에 삽입할 때 단순히 큐의 맨뒤에 push 했다. 또한, 다익스트라의 경우도 우선순위 큐를 사용하여 항상 최솟값 또는 최댓값이 pop 되게 했다.(내부적으로 정렬된건 아니지만)

 

0-1 BFS의 경우는 deque를 사용한다.

• 가중치가 있는 지점을 탐색할 때 : 기존 값 +1 
  • 덱의 맨 위에 삽입(append)
• 가중치가 없는 지점을 탐색할 때 : 기존값 유지 
  • 덱의 맨 앞에 삽입 (appendleft)

이렇게 함으로써 가중치가 낮은 지점부터 먼저 탐색하는 것을 더욱 효율적으로 할  수 있다.

 

 

문제 해결

 

이 문제는 제 3자 (문제에서는 상근이)가 같이 낌으로써 좀 어려웠다. 3번의 bfs 탐색을 하고 나온 결과로 답을 구해야 했다.

• 1번 죄수의 위치에서 탈출하기
• 2번 죄수의 위치에서 탈출하기
• 상근이의 위치에서 탈출시키기

1, 2번 죄수의 위치에서 탈출은 해당 좌표를 시작점으로 해서 계산하면 되지만, 상근이가 밖에서 문을 열어주는 부분을 고려해야한다. 

 

이를 위해 입력받은 맵의 테두리에 1줄씩 추가했다. 그렇게 하면 상근이는 (0, 0)에서 출발하여 탐색을 시작하므로, 밖에서 문을 열어주는 것을해결할 수 있다. 이렇게 나온 결과값은 해당 지점까지 오기까지 몇개의 문을 열었는 지를 알려준다.

 

단, 문($)의 경우 1명만 열면 나머지 2명은 자연스레 나올 수 있으니 -2를 해주는 것이 포인트다.

 

소스코드

 

import sys
from collections import deque

tc = int(input())

dy = [-1,1,0,0]
dx = [0,0,-1,1]

def bfs(y, x):
    visited = [[-1]*(w+2) for _ in range(h+2)] # 맵의 외곽을 추가, 열어야 하는 문의 개수
    dq = deque()    
    dq.append([y,x])
    visited[y][x] = 0
    while dq:
        y, x = dq.popleft()
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if 0<= ny <= h+1 and 0 <= nx <= w+1:
                if visited[ny][nx] == -1:
                    if board[ny][nx] == '.' or board[ny][nx] == '$': # 문을 안열고 진행
                        visited[ny][nx] = visited[y][x]
                        dq.appendleft([ny, nx]) # 가장 앞에 삽입 
                    elif board[ny][nx] == '#': # 문을 여는 경우
                        visited[ny][nx] = visited[y][x] + 1
                        dq.append([ny, nx])
    return visited

for _ in range(tc):
    h, w = map(int, input().split())        
    board = [list('.'*(w+2))] # 맨 윗줄 추가
    for i in range(h):
        board.append(list('.'+ input().strip() + '.'))
    board.append(list('.'*(w+2))) # 맨 아랫줄 추가

    prisoner = []
    for i in range(h+2):              
        for j in range(w+2):
            if board[i][j] == '$':
                prisoner.append([i,j])
    
    one = bfs(prisoner[0][0], prisoner[0][1])
    two = bfs(prisoner[1][0], prisoner[1][1])
    sang = bfs(0, 0)
    answer = sys.maxsize

    for i in range(h+2):
        for j in range(w+2):
            if  one[i][j] != -1 and two[i][j] != -1 and sang[i][j] != -1:
                result = one[i][j] + two[i][j] + sang[i][j] # 해당 위치에서 문을 여는 개수
                if board[i][j] == '*': # 벽은 제외
                    continue
                if board[i][j] == '#': # 한명만 열어도 되기 때문에 나머지 사람이 연 갯수인 2를 빼줌
                    result -= 2
                answer = min(answer, result)
    print(answer)