다익스트라 알고리즘
-
[백준][Kotlin] 1916번 최소비용 구하기백준 2023. 4. 20. 15:58
해당문제는 다익스트라 알고리즘을 사용하여 작성 할 수 있었습니다. 다익스트라 알고리즘은 거리배열과 우선순위큐를 이용하여 가중치가 적은 자료부터 확인하는 로직,그리고 방문했던 노드 재방문 방지 등에 대한 로직에 대한 이해를 하고 있다면 쉽게 작성할 수 있는 알고리즘이라고 개인적으로 생각이 듭니다. 해당 문제는 코드 내에 주석을 이용하여 설명을 적어 쉽게 이해 할 수 있도록 하였습니다. 하기는 제가 작성한 코드와 제출 결과 입니다. import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.util.* import kot..
-
[백준][Kotlin]1753 최단경로백준 2023. 4. 20. 15:26
해당 문제는 다익스트라 알고리즘을 이용하여 작성 할 수 있습니다. 다익스트라 알고리즘은 노드별로 가중치가 있고 가중치가 0 이상의 양수 일 때 사용가능 하며, 출발 노드로 부터 특정 노드까지의 최단 거리를 구할 때 사용합니다. 작성 포인트로는 첫번째. 인접 리스트로 그래프 구현하기 두번째. 최단 거리 배열 초기화 하기 세번째. 값이 가장 작은 노드 고르기 네번째. 최간 거리 배열 업데이트 하기 두번째 포인트에 맞춰 최단 거리 배열을 초기화 할 때 추 후 값이 작은 값을 선택해야 하므로 그나마 무한대에 가까운 값을 넣어 초기화 합니다. 만약 입력값의 최대 범위가 Int 일 경우에는 Int.MAX_VALUE 로 초기화 하여도 됩니다. 세번째 포인트의 경우 우선순위큐를 이용하여 가중치가 적은 순 부터 비교하면..