다익스트라

다익스트라(Dijkstra) 알고리즘 DP를 활용한 최단 경로 탐색 알고리즘 다익스트라 알고리즘은 특정한 정점에서 다른 모든 정점으로 가는 최단 경로를 기록한다. 여기서 DP가 적용되는 이유는, 굳이 한 번 최단 거리를 구한 곳은 다시 구할 필요가 없기 때문이다. 이를 활용해 정점에서 정점까지 간선을 따라 이동할 때 최단 거리를 효율적으로 구할 수 있다. 다익스트라를 구현하기 위해 두 가지를 저장해야 한다. 해당 정점까지의 최단 거리를 저장 정점을 방문했는 지 저장 시작 정점으로부터 정점들의 최단 거리를 저장하는 배열과, 방문 여부를 저장하는 것이다. 다익스트라의 알고리즘 순서는 아래와 같다. 최단 거리 값은 무한대 값으로 초기화한다. for(int i = 1; i

[백준 1261] 알고스팟 문제 출처 : 링크 경로를 이동하는 걸 생각하면 DFS나 BFS를 활용해야 될 것 같다. 하지만 기존의 문제와는 다르게, '가중치'가 존재한다. 1인 값을 가지고 있는 곳을 지날 때는 벽이 있는 것이므로 부수고 지나갈 수 밖에 없다. 따라서 그냥 움직이는 것이 아닌, 1인 곳을 지나갈 때마다 값을 변경시켜나가야 하는 문제다. 우선 미로탐색처럼 BFS와 유사한 방식으로 나아가지만, 이 가중치 값을 최소화 시키기 위해 그냥 큐가 아닌 우선순위 큐를 사용해서 저장한다. (우선순위를 위해 comperable 활용) 123456789101112131415161718class Spot implements Comparable{ int y; int x; int cost; public Spot..

[알고리즘] 다익스트라(Dijkstra) 다익스트라(Dijkstra) : 하나의 선택한 정점에서 각 정점까지 갈 수 있는 최단거리를 구하는 알고리즘 경로를 찾을 때 가중치가 있으면 사용하자 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657import java.util.Arrays; /** * Dijkstra : 하나의 선택한 정점에서 각 정점까지 갈 수 있는 최단거리를 구하는 알고리즘 * * Greedy 방식, 음이 아닌 가중치일 경우만 사용가능 * 음의 가중치가 있는 경우 => 벨만포드 알고리즘을 통해서 구해야 한다 * 시간복잡도 O[n^2] */ public cl..