최소비용 구하기 19161 [6개월 안에 백준 플래티넘 달성하기] 9. 최소비용 구하기 1916 | 코틀린 Class 4에서 처음으로 접하게 된 그래프 알고리즘인 다익스트라 문제입니다. 다익스트라의 기본 개념을 알고 있고 몇 개의 반례 케이스만 해결한다면 쉽게 풀 수 있습니다. 문제 풀이 사실 다익스트라에 대한 개념이 없어도 bfs + 우선순위 큐 를 잘 활용하면 문제를 풀 수 있습니다. A에서 B까지의 최소 비용을 구하기 위해서는 결국 A에서부터 BFS로 최소 비용을 구하면서 B에 도달하면 됩니다. 추가적으로 주의해야 할 반례 케이스가 두 가지 있습니다. 첫 번째로 버스 비용이 0인 경우가 가능합니다. 따라서 초기화 시점에 값을 0으로 지정하면 안 됩니다. 두 번째로 동일한 버스 노선에 여러 비용을 주는 경우가 있습니다. 이 경우에는 여러 비용 중 최소 비용을 추가하도록 코드를 수정해 주면 됩니다. 반례 모.. 2023. 11. 27. 이전 1 다음 반응형
