[백준9376] 탈옥

문제

---

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

9376번: 탈옥

 

생각의 흐름

---

사실 혼자 힘으로 풀지 못해 블로그를 많이 참고해서 구현하였다. 참고한 블로그는 https://rebas.kr/770이다. 위 블로그에 드러나지 않은 부분을 설명하겠다. bfs함수의 for문 안에서 '.'인 경우 appendleft를 해주고 '#'인 경우 그냥 append를 해주는데 이유는 '.'인 경우를 우선적으로 처리하도록 하기 위함이다. 왜냐하면 '.'와 연결된 경우는 문을 부수지 않고 갈 수 있는 것이니 이전과 같은 숫자를 리스트에 저장해야 한다. 만약 '#'를 먼저 처리하도록 하면 굳이 문을 부수고 가지 않아도 되는 위치를 문을 부수고 가도록 하게 된다.

 

코드

---

# BOJ 9376

from collections import deque

def bfs(x,y):
    dist = [[-1]*(w+2) for _ in range(h+2)]   # 방문체크하고 갱신하기 위한 용도
    q = deque()
    q.append((x,y))
    dist[x][y]=0
    while q:
        x, y = q.popleft()
        for dx, dy in (-1,0),(1,0),(0,-1),(0,1):
            nx, ny = x+dx, y+dy
            if nx < 0 or nx > h+1 or ny < 0 or ny > w+1:
                continue
            if dist[nx][ny]>=0 or maze[nx][ny]=='*':
                continue
            if maze[nx][ny]=='#':
                dist[nx][ny]=dist[x][y]+1
                q.append((nx,ny))
            elif maze[nx][ny]=='.':
                dist[nx][ny]=dist[x][y]
                q.appendleft((nx,ny))

    return dist


for _ in range(int(input())):
    h, w = map(int, input().split())
    maze=[]
    maze.append(list('.'*(w+2)))
    for _ in range(h):
        maze.append(list('.'+input().strip()+'.'))
    maze.append(list('.'*(w+2)))
    dq = deque()
    for i in range(h+2):
        for j in range(w+2):
            if maze[i][j]=='$':
                maze[i][j]='.'
                dq.append((i,j))
    sx, sy = dq.popleft()
    d1 = bfs(sx, sy)
    sx, sy = dq.popleft()
    d2 = bfs(sx, sy)
    d3 = bfs(0, 0)
    ans = 1000000000
    for i in range(h+2):
        for j in range(w+2):
            if maze[i][j]=='*':
                continue
            k = d1[i][j] + d2[i][j] + d3[i][j]
            if maze[i][j]=='#':
                k-=2
            ans = min(k,ans)

    print(ans)