[백준1261] 알고스팟

문제

---

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

1261번: 알고스팟

 

생각의 흐름

---

1. (0,0)을 시작점으로 보고 (n-1, m-1)칸, 다시말해 우측 맨 하단의 칸을 도착지점으로 보고 최단경로를 찾기 위한 다익스트라 알고리즘을 적용하면 된다.
2. 이 때, 1이 있는 곳으로 이동할 때에는 벽을 부숴야 하기 때문에 가중치가 1인 것으로, 0인 곳은 가중치가 0인 것으로 보면 된다.
3. 어려운 부분은 최단거리를 계산해야 한다는 것인데 이를 위해 priority queue를 사용하여(이 때, 우선순위에 대한 기준은 해당위치까지 도달하기 위한 cost가 된다.) cost가 가장 짧은 경로를 우선적으로 추출하여 처리한다는 것이다. 

사실 처음에는 순열을 이용한 방식으로 접근을 하였다. 간단히 말해서 우측으로 가는 걸 1, 아래로 가는 걸 0이라 하고 (행의 갯수-1)만큼의 0과 (열의 갯수-1)만큼의 1을 리스트에 집어넣어 permutations를 사용하여 경로별 cost를 계산하고 이 중 최솟값을 찾자는 아이디어다!!! 이 접근법은 일단 논리적으로는 맞다. 실제로 여러 개의 testcase들도 통과하는 것을 확인하였다.

하지만 문제의 조건에서 행과 열의 최대갯수가 100까지 되는 상황에서 이러한 방식은 메모리초과가 생겨서 실패 ㅜㅜ 결국 다익스트라를 사용하는 방법으로 (인터넷을 참고하여^^)풀게 되었다.

 

깨달은 점

---

그 동안 다익스트라 알고리즘을 정석대로 그래프로 주어진 데이터에 대해서만 적용하는 것으로 생각했었는데 이처럼 행렬로 주어진 경우에도 BFS, DFS를 이용하여 탐색을 하면서 해당 알고리즘을 적용할 수 있다는 사실을 깨달았다.

중요한 부분이므로 추후에 MST 알고리즘들의 차이점에 대해서도 따로 정리를 해두어야겠다.

 

코드

---

from queue import PriorityQueue as pq
def dijkstra(): 
    heap = pq() 
    heap.put((0, (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)))
                else:
                    heap.put((cnt, (x, y)))
                    
m, n = 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])