[백준알고리즘] 1261번: 알고스팟 -Python

[백준알고리즘] 1261번: 알고스팟 -Python

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

1261번: 알고스팟

굉장히 난감했던 문제인데 다른 분들의 코드도 보니 별거 아니었다.

 

우선은 처음에는 그냥 DFS(백트래킹) 혹은 BFS 방식으로 문제를 풀려고 했다. 하지만 문제의 경우 이미 방문했던 좌표라고 할지라도 어디로부터 방문했는지에 따라서 해당 좌표까지 이동하면서 벽을 부순 횟수가 달라졌다.

 

예를 들어 다음과 같이 있을 때, 일반적인 BFS방식으로는 (2, 0)까지의 거리는 1이 되겠지만, (2, 0)까지 벽을 부순 최소 횟수는 0이다.

00
10
00

 

 

따라서 일반적인 DFS, BFS방식으로는 문제를 해결할 수 없다고 생각했다. 중복 방문을 허용하는 순간 BFS, DFS 방식이라 볼 수 없을뿐더러 결국 (0, 0)에서 각 좌표까지 가는 모든 경로를 확인하는 것처럼 시간이 굉장히 많이 소요될 것이기 때문이다.

그 정도는 아니지만

 

아무튼 그러다 보니 DP를 생각하게 되었다. 하지만 DP 또한, 주어진 방향에서만 오는 것이 아니기 때문에 문제가 생겼었다. 특정한 규칙, 점화식을 만들고 적용할 수 없다고 생각했다. 예를 들어 모든 방향을 고려하기 위해서 다음과 같이 점화식을 짠다면 무한 루프에 빠지기 때문이다.

cnt[i][j] = min(dp(i-1, j), dp(i+1, j), dp(i, j-1), dp(i, j+1))

 

 

도저히 시간 안에 푸는 방법이 생각 안 나서 알고리즘 분류를 확인했다. 사용해야 하는 알고리즘은 다익스트라 알고리즘 (Dijkstra Algorithm)인 것을 확인했다.

 

다익스트라 알고리즘은 매 step마다 방문할 수 있는 경로 중에서 가장 작은 비용인 경로를 선택해서 이동하고, 주변의 다른 지점의 경로를 update해가는 알고리즘이다. 주로 그래프에서 하나의 지점에서 모든 지점까지 최소 비용으로 도착할 수 있는 트리를 만들 때 사용한다. 위키피디아 링크는 여기고, 구글에 검색해서 다른 블로그들을 참조하는 것이 이해는 더 쉬워 보인다.

 

 

아무튼 다익스트라 알고리즘으로 문제를 해결하기 위해서 queue 모듈의 PriorityQueue를 사용했다. heapq 모듈을 사용해 heappop()과 heappush()을 사용하며 벽을 부순 횟수로 가중치를 두어 min heap을 사용해도 똑같이 구현할 수 있다.

 

처음에 말했다시피 통과하고 다른 분들의 코드를 보니 BFS로 중복방문을 통해 값을 갱신해나가는 코드들이 더 짧은 시간들에 통과해있었다. 게시판을 통해 확인하니 의도는 다익스트라 알고리즘으로 해결하기 위한 것이었으므로 보나 테스트 케이스의 크기가 작아서 중복 방문을 통한 계산도 통과되는 것으로 보인다고 한다.

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 heap:
        cnt, (hi, hj) = heap.get()
        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] = cnt

                if maze[x][y] == '1':
                    heap.put((cnt+1, (x, y)))
                else:
                    heap.put((cnt, (x, y)))

m, n = map(int, input().split())
maze = [list(input().rstrip()) for _ in range(n)]
crush = [[-1] * m for _ in range(n)]

dijkstra()
print(crush[n-1][m-1])

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다