[백준2178] 미로 탐색

문제

---

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

2178번: 미로 탐색

 

생각의 흐름

---

이전에 포스팅했던 알고스팟과 유사한 문제이다. 차이점은 2가지이다.

1. 시작점과 끝점의 칸 수를 포함하여 계산한다는 점
2. 알고스팟의 경우 칸의 수가 1인 경우와 0인 경우 모두 이동이 가능했지만 본 문제의 경우 1인 경우에만 이동이 가능하다는 점

 

코드

---

from queue import PriorityQueue as pq
def dijkstra(): 
    heap = pq() 
    heap.put((1, (0, 0))) 
    crush[0][0] = 0 
    # 상하좌우
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] 
    while True:
        cnt, (hi, hj) = heap.get() 
        # print(cnt, hi, hj)
        if hi == n-1 and hj == m-1:
            break
        for d in range(4):
            x, y = hi + dx[d], hj + dy[d]
            if 0<=x<n and 0<=y<m and crush[x][y]<0:
                # crush[x][y] = (x,y)전까지 부순 벽의 갯수
                crush[x][y] = cnt
                if maze[x][y] == '1':
                    # heap의 원소의 cnt = (x,y)에서 부순 벽의 갯수도 포함
                    heap.put((cnt+1, (x, y)))
                    
n, m = map(int, input().split())
maze = [list(input()) for _ in range(n)]
crush = [[-1] * m for _ in range(n)]
dijkstra()
print(crush[n-1][m-1]+1)