최단 경로의 핵심 최단 경로 알고리즘에는 다양한 종류가 있음. 우선 , 한 지점에서 특정 지점으로 까지의 최단 경로를 구해야하는 경우 모든 지점에서 모든 지점까지의 최단 경로를 구해야 하는 경우 경우를 생각해본다. 또, 최단 경로의 합을 구하는 경우 최단 경로에서 거쳐온 노드들을 구하는 경우 를 캐치 한다. 🔑 앞서 공부한 그리디, 다이나믹은 최단경로 알고리즘에서 그래도 적용 된다. 다익스트라 알고리즘: 기준 노드에서 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하여 갱신한다는 특징이 있다. 방법 1. 구현하기 쉽지만 느리게 동작하는 다익스트라 O(n^2) 방법 2. 구현하기 조금 어렵지만 빠르게 동작하는 다익스트라 (우선순위 힙 이용) O(elogv) 플로이드 알고리즘 : 2차..

[Java] UVa 10150 더블릿(Doublets) 문제 onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1091 Online Judge 10150 - Doublets Time limit: 3.000 seconds onlinejudge.org 문제 설명 내 코드 🎨 Key Point 이 문제가 BFS 최단경로 알고리즘을 써야하는 이유는 최단 경로를 찾으라고 하였기 때문이다. 답은 여러개가 나올 수 있으나 최단 경로를 찾으라 하였다