[백준 알고리즘][다익스트라] 1753번 최단경로

문제 정의

방향그래프가 주어질 때 주어진 시작점에서 다른 모든 정점으로의 최단 경로의 경로값을 구해야한다. 

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1753)

문제 풀이

다익스트라 알고리즘을 사용해서 각 정점으로의 최단 경로를 구할 수 있다. 우선 주어진 입력을 통해서 인접리스트를 만들고, 다익스트라 알고리즘을 수행하면된다. 그런데 아직 가중치가 주어진 그래프를 벡터로 표현해서 사용해본적이 없어서 벡터를 통해 인접리스트를 만들 때 가중치를 어떻게 저장해야할지 생각해보아야 한다. 가장 쉽게 생각을 하면 각 정점에서 어느 정점으로 갈지를 나타내는 수와 가중치를 함께 저장할 수 있도록 pair를 사용해봐야겠다. 인접리스트를 만든다음에는 시작점에서부터 다익스트라 알고리즘을 수행하며 각 정점으로의 최단거리를 갱신해나가야한다. 최종적인 최단 경로의 경로값을 구하는 것이기떄문에 각 정점의 parent를 저장해둘 필요는 없고, 각 정점을 방문했는지를 체크해주는 배열은 필요하다. 다익스트라를 수행하기위해서는 우선순위 큐를 사용해서 방문하지 않은 정점이며, 가장 작은 경로값을 가지고 있는 정점을 선택하여서 최단 경로를 갱신해나가야 한다. 

+추가 2018.11.11

다익스트라 알고리즘을 다시 짜봐야겠다고 생각을 하고 풀면서 이번엔 vector도 사용안하고 priority_queue도 안사용하고 직접 짜보자 생각이 들었다. 힙이나 인접리스트는 자료구조 배울 때 공부했었지만 막상 지금 짜려고하면 어버버할 것 같아서 복습 겸 해보기로 했다. 링크드리스트를 구현하고 힙을 구현해서 예제를 맞추는 것 까지는 성공했다. 분명 그런데 잘못 짠 부분이 있는지 답을 제출하면 틀렸습니다만 나왔다. 질문검색에서도 테스트케이스가 몇개 없어서 확인하는데 어려움이 있었다. 그래서 내가 여러 케이스를 만들고 디버깅하면서 고쳐나가야겠다고 생각했다. 문제를 구현한 부분을 크게 3가지로 나누었을 때 그래프를 저장하는 인접 리스트, 다익스트라 알고리즘 자체, heap으로 구현한 우선순위 큐인데 이 중 어느 부분이 틀렸는지 찾는 것이 우선이었다. 그래서 우선 heap이 잘 구현됐는지 확인하고 싶어서 min heap 문제를 찾아서 그 부분만 제출해봤다. 여기서부터 틀려있었다. 한줄이 잘못 구현되었었는데 계속 넣어보는 케이스에서는 문제가 없어서 못찾을 뻔 했다. 바로 고치고 그 다음은 다익스트라 알고리즘 자체가 잘못되었는지 확인해보려고 내가 구현한 인접 리스트대신 vector를 사용하고 heap대신 priority_queue를 사용해서 제출해봤다. 그러니 바로 맞았습니다를 받았다. 다익스트라 알고리즘 자체는 문제가 없다는 걸 알았고 링크드리스트로 구현한 인접리스트를 고쳐야겠다고 생각을 했다. 이 최단경로 문제에서는 (u, v)를 이어주는 간선이 여러개일수도 있는데 이 부분에서 인접리스트를 잘못 사용해준 부분이 있었다. 결국 3가지의 방법으로 다시 테스트해보고 맞았습니다를 받을 수 있었다. (= 3가지를 STL없이 구현해서 풀었다!) STL 쓸 때 고려할 필요없었던 사이즈문제 때문에 틀린 이유도 있었다. 지난번에 풀었을 때 문제도 틀렸습니다였는데 그 당시에는 무한대 값을 너무 작은 것으로 초기화해서 생긴 문제였다. 앞으로는 좀 더 문제조건을 꼼꼼히 읽고 틀렸습니다를 적게 받도록 해봐야겠다. STL은 아주 편리하다는 걸 새삼 깨닫는다.