mondegreen

가중치가 있는 그래프 문제이다. 다익스트라 알고리즘을 활용해야 하므로 우선순위 큐로 구현해야 한다. 이 때 delivery라는 클래스는 정렬 기준을 선언해줘야 한다. 주의할 점은 무방향 그래프이기 때문에 인접리스트에 양방향으로 값을 넣어줘야 한다. 오랜만이다 다익스트라..!ㅎ import java.util.*; class Solution { public static class delivery{ int dest; int time; public delivery(int x, int y){ this.dest = x; this.time = y; } } public int solution(int N, int[][] road, int K) { int answer = 0; int [] dist = new int[N+1..

최단 경로의 개념 간선의 가중치가 있는 그래프에서 "두 정점 사이의 경로들 중"에 간선의 가중치의 합이 최소인 경로 1) 다익스트라(음의 가중치 허용하지 않음) 2) 벨만-포드(음의 가중치 허용함) 다익스트라의 개념 시작 정점에서 끝 정점까지 거리가 최소인 정점을 선택해가며 최단 경로를 구하는 방식 프림과 유사하나 당장의 가중치 한 개의 값이 아닌 "가중치의 합"을 고려해야 하는 알고리즘이다. 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. 다익스트라 동작 과정 1) 시작 정점 선택 2)..