다익스트라
BOJ 1753 최단경로 [Java]
BOJ 1753 최단경로 1. 문제 링크 https://www.acmicpc.net/problem/1753 2. 문제 해설 다익스트라 알고리즘을 이용하는 기본 문제이다. 다익스트라 알고리즘 구현을 연습하기에 좋았다. 코드 구현에 대한 설명은 아래 다익스트라 알고리즘에 대해 써놓은 글을 참고해보자. [최단 거리 알고리즘 - 다익스트라 [Java]] 3. 코드 보기 import java.io.*; import java.util.*; public class Main { static class Node implements Comparable { int vertex; int distance; public Node(int vertex, int distance) { this.vertex = vertex; this.d..
최단 거리 알고리즘 - 다익스트라 [Java]
목차 1. 서론 2. 작동원리 3. 구현 1. 서론 다익스트라 알고리즘은 한 정점에서 다른 정점들까지의 최단 거리와 경로를 구하는 알고리즘이다. 단, 간선의 거리 정보는 항상 0 이상이어야 한다. 2. 작동원리 1. 방문하지 않은 정점 중 가장 시작점으로부터 거리가 짧은 정점으로 이동한다. 이 때, 해당 정점까지의 최단 거리는 확정된다. 2. 현재 정점과 인접한 모든 정점들 중 방문하지 않은 정점들을 돌면서 거리를 갱신시켜준다. 즉, 현재 정점까지의 최단 거리를 A, 현재 정점과 인접한 정점 V를 잇는 간선의 거리를 B, 현재까지 구한 V까지의 최단거리를 C라고 했을 때, A+B < C 이면 V까지의 최단 거리를 A+B로 갱신해준다는 의미이다. 위 과정을 아래에서 그림으로 한번 살펴보자. 아래 그림은 영..