다익스트라 알고리즘 설명 및 백준 1753 문제 풀이 https://chb2005.tistory.com/78 [JAVA] 다익스트라 (Dijkstra) (+ Priority Queue을 사용한 시간 단축) Dijkstra 란? 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘 단, 가중치에 음수가 있으면 사용할 수 없음 시간복잡도 : O(E logN) (N:노드의 수, E: 간선의 수) 다음과 같은 그래프가 있 chb2005.tistory.com

문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 해결 방법 n개의 노드가 주어지고 모든 노드에서 노드 X로 갔다 오는 최단 거리를 구해야 함 모든 노드 -> 노드 X + 노드 X -> 모든 노드 와 같이 2부분으로 나누어 생각해 봄 노드 X -> 모든 노드의 최단 경로는 다익스트라 알고리즘을 사용 ( 다익스트라 -> https://chb2005.tistory.com/78 ) 모든 노드 -> 노드 X로 가는 최..

Dijkstra 란? 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘 단, 가중치에 음수가 있으면 사용할 수 없음 시간복잡도 : O(E logN) (N:노드의 수, E: 간선의 수) 다음과 같은 그래프가 있다고 가정 1번 노드에서 2, 3, 4, 5번 노드까지의 최단거리를 모두 구해야 함 dist[1~5] = [0, ∞, ∞, ∞, ∞]로 초기화 후 시작 1번 노드에서 갈 수 있는 노드 = 2, 3, 4 1(시작노드) -> 2로 갈 때 드는 비용 ( = dist[1] + (1->2) )과 지금까지 2로가는 최소 비용 (=dist[2])를 비교해서 지금까지 2로가는 최소비용이 더 크다면 dist[2] = dist[1] + (1->2)로 갱신 이 방식으로 1번노드에서 갈 수 있는 노드들에 대한 ..