[1916] 최소비용 구하기

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

1916번: 최소비용 구하기

다익스트라 알고리즘을 통해 풀 수 있다.

 

풀이

출발 노선 지점에서 각 지점으로의 최소비용을 담을 dist:[Int]() 배열을 생성한다. 이후 입력되는 노선의 정보를 저장한 후 너비 우선 탐색을 통해 다음 노선까지의 비용이 더 저렴하다면 dist 원소 값을 경신한 후 값이 경신된 해당 지점을 큐에 담아 다음 탐색 경로에 추가해주면서 탐색을 수행하면 된다.

참고해야 할 점은 입력받은 노선 정보를 비용 기준 오름차순 정렬해주어야 한다는 점이다. 다익스트라 알고리즘의 조건인 최소비용부터 탐색한다는 조건을 생각하지 못해 정렬하지 않은 채로 제출했었는데 시간 초과가 일어났었다. 곰곰이 생각해보니 A -> B로 가는 노선이 여러 개일 경우 정렬을 하지 않은 채로 탐색을 수행한다면 큐에 중복된 경로를 추가하게 되어 불필요한 탐색을 수행하게 된다.

 

정답 코드