[BOJ] 11779 최소비용 구하기 2 (C/C++)

11779번: 최소비용 구하기 2

문제

n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.

입력

첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

둘째 줄에는 그러한 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력한다. 출발 도시와 도착 도시도 포함한다.

셋째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력한다.

---

제목만 보고는 MST를 구하는 문제인줄 알았는데, 그게 아니라 shortest path를 구해야 했다. shortest path에서 가장 많이 사용하는 알고리즘은 플로이드와 다익스트라가 있다. 둘의 시간 복잡도는 플로이드가 O(N^3)이고 다익스트라는 O(N^2)(힙을 사용하면 O(NlogN)까지 줄일 수 있음)이다. 이 문제에서는 최단 경로를 여러 번 구하지 않으므로 다익스트라를 사용하는 것이 좋다고 생각했다.

 

여기까지 생각한건 좋았는데 막상 다익스트라를 코드로 옮기려니 막상 생각이 잘 안 났다. 부분 부분 기억은 나는데 정확히 잘 모르겠더라. 다익스트라 정도는 이제 눈 감고도 써줘야 될 것 같은데 아직도 이 모양이다. 그래서 다익스트라의 세부적인 구현만 다른 사람들의 블로그를 참고했다.

 

이후에 방문 경로를 출력하기 위해서 백트레이싱을 해야겠다는 생각이 들었다. 어떤 방법이 있을까 고민하다가 어떤 노드의 최단 경로를 결정하기 전에 방문했던 노드를 저장해놓으면 도착점에서 시작점까지 거꾸로 올 수 있을 것 같았다. 그래서 prev_node라는 배열을 만들어서 이전 노드를 저장하고 이후에 다익스트라 알고리즘이 끝난 이후에 경로를 거꾸로 가면서 스택에 노드를 담았다. 마지막으로 스택 크기와 스택에 담겨있는 값들만 출력하면 끝난다.

 

문제를 다 풀었는데 최단 경로가 예시보다 오히려 더 적게 나왔다. 대충 그래프를 그려봤을 때에도 이 출력값이 맞는 것 같아서 좀 더 시간이 필요했다. 알고 보니 내가 간선의 방향을 설정하지 않고 양방향 간선으로 입력을 받기 때문에 생긴 문제였다. 한쪽 간선을 끊어주니 바로 pass를 받았다.

 

 

후기)

다익스트라 알고리즘 마냥 잘 기억나지 않는 알고리즘이 많다. 그래프에서 사용하는 알고리즘만해도 당장 이름이 떠오르는게 4개 정도되는데 다 구현해보라고 하면 좀 걸릴듯...? 참 망각의 동물이다.