알고리즘
다익스트라 (Dikjstra) (with. 백준 1916)
Notion - 다익스트라 이번에는 다익스트라에 대해 정리하고, 문제를 기준으로 이해해보자. https://www.acmicpc.net/problem/1916 - 최소비용 구하기 / Gold 5 위 문제의 예제인 아래 입력을 기준으로 설명해보도록 하겠다.581 2 21 3 31 4 11 5 102 4 23 4 13 5 14 5 31 5다익스트라 알고리즘?다익스트라는 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다.다익스트라는 2중 for문을 이용한 방법, 우선순위 큐를 이용한 탐색으로 구현 방법이 나뉜다.그럼 이번에도 그림으로 표현해보도록 하겠다. 이전 글인 플로이드 워셜과 유사하게 접근이 가능하다.INF를 사용하지만 이번에는 시작 지점만을 위한 가중치 배열인 dist를 따로 선언하여 사..
