[Java]백준 1753 다익스트라
출처 https://www.acmicpc.net/problem/1753 접근 각 정점에서 다른 정점으로의 최솟값을 다익스트라1를 통해 구합니다. 정점으로부터 최단거리의 간선으로만 이동하기 때문에 O(ElogV) ≈ 1,200,0002으로 모든 간선을 확인하는 것이 가능합니다. 탐색하는 간선 개수를 최적화하기 위해 LinkedList로 저장합니다.3 문제에서 주어진 예제를 그래프로 표현했습니다. 그래프 1 2 3 4 5 초기화 0 INF INF INF INF 1 -> 2, 3 0 2 3 INF INF 2 -> 3, 4 0 2 3 7 INF 3 -> 4 0 2 3 7 INF 5 -> 1 0 2 3 7 INF 위와 같이 거리 배열을 초기화한 후, 각 정점의 간선들을 탐색하며 배열을 채워나갑니다. 이 때, Greedy 알고리즘인 다익스트라가 도입되는데, 각 지점에서 가중치의 최솟값인 경로만 선택하면서 목표지점까지 이동하면 최소 경로를 구할 수 있다는 것입니다. ...