[백준] 코딩테스트 문제 풀이 : 1753.최단경로 #Daijkstra#Heap#PriorityQueue#Graph

[문제]

[접근 방법]

전형적인 다익스트라 알고리즘 문제이다. 최근에 DFS/BFS에 대해 공부하고 있는데 내가 그래프에 많이 약하다는 것을 알아서 더 열심히 하려고 한다. 다익스트라 알고리즘에 대해 알게 되어 연습할 겸 다익스트라 알고리즘 문제를 풀어보았다. 한 정점에서 다른 정점까지 이동하는 최단 거리를 구할 때, 모든 간선의 비용(가중치)이 양수라면 다익스트라 알고리즘으로 문제를 해결할 수 있다.(음수라면 벨만 포드 알고리즘을 이용해야 한다.)

문제에서 출발점은 매번 다르게 주어지고 그 출발점을 기준으로 연결된 간선을 통해 이동할 수 있는 노드 중 간선의 비용이 가장 적은 것을 가장 먼저 방문하며, 거리 테이블을 만들어 매번 새 노드를 방문할 때마다 거리 테이블을 갱신해준다. 이 때 중요한 점은 방문할 노드의 순서는 아직 방문하지 않은 노드 중 간선의 비용 정보가 적은 노드를 방문한다는 것이다. 이 때 단순 큐가 아니라 우선순위 큐를 활용해야 방문해야 하는 노드의 수가 10000개, 20000만 개가 되어도 1초 내의 수행 시간을 보장할 수 있다.

처음에는 꼼수(?)를 쓰기 위해 단순히 우선순위 큐를 이진 탐색으로 구현하려고 했다. 하지만, 이진 탐색으로 우선순위 큐를 구현하면 탐색하는 데에는 O(lgN)의 시간 복잡도일지 몰라도 배열 원소 삽입과 삭제에 최악의 경우 O(N)시간이 걸린다는 단점이 있다. (splice를 사용하므로 단순히 pop()과 push()라면 시간이 적게 걸리겠지만 splice()를 쓰면 중간의 원소를 삭제할 때 뒤의 원소를 다 당겨서 재배열 해야 하는 시간이 걸린다.) 그러므로 당연히 시간초과가 났고, minheap을 직접 구현하여 문제를 해결했다.(보석 도둑은 실패했지만, 최단 경로는 자바스크립트! 통과했습니다. 여러분 함께 기뻐해주십쇼✨) 다익스트라 알고리즘 구현 중 깔끔하다고 생각했던 건, 현재 거리 테이블의 저장된 노드의 비용보다 큐에 삽입된 비용이 더 크다면 visited된 것으로 간주해서 따로 visited 배열을 사용하지 않는다는 점이다.

처음에 실수했던 부분은 다음 노드의 거리 배열에 저장된 해당 노드의 최소 비용과 현재 노드를 거쳐서 갈 경우 새로 갱신되는 비용을 비교해서 더 작은 경우에만 비용 테이블과 우선순위 큐에 삽입을 해줘야 하는데 단순이 Math.min(다음 노드 거리 배열 값, 현재 노드 비용 + 다음 노드까지의 간선 비용)을 계산해 다 업데이트하고 큐에 추가해서 메모리 초과가 났다. 노드의 수가 많기 때문에 해당하는 경우만 처리를 해줘야 메모리 초과와 시간 초과를 피할 수 있는데 이 점을 간과했던 것이 실수.

다음 실수는 정말 말도 안 되는 데서 실수를 했는데, 우선순위 큐를 구현하는 부분에서 원소를 삭제한 경우 가장 마지막 원소를 queue[0] = queue.pop()하고 자식 노드와 비교해서 더 큰 경우 자식 노드와 위치를 바꾸는 bubbleDown()을 수행해야 하는데, 이 때, leftChild = 2 * parent + 1, rightChild = 2 * parent + 2 를 해줘야 하는데, rightChild에 + 1을 해줘서 틀린 값이 계속 나왔다.

정말 간단한 코딩 실수를 해서 스스로 너무 어이가 없었고 반성 했다. 이런 기초적인 실수는 정말 피해야만 한다.

[해결한 코드]

첫 번째 제출 때는 그냥 console.log()로 출력을 했는데, 그러다 보니 시간이 많이 걸렸다. 다른 분이 print함수를 따로 만드신 걸 보고 그렇게 바꿔서 제출했더니 풀이 시간이 절반으로 줄어들었다. 앞으로는 출력이 많으면 단순 console.log보다 print function을 만들어서 string으로 출력하면 더 좋을 것 같다.