이번 포스트에서는 알고리즘 문제에 자주 나오는 "최단 경로"문제를 해결하기 위한 알고리즘들에 대해서 살펴보자. 최단 경로란? 최단 경로란 그래프를 탐색하면서 임의의 두 정점 사이에 다양한 간선의 조합 중 간선의 가중치의 합이 최단인 경로를 의미한다. 이 최단거리를 구할 때는 크게 간선의 가중치가 없는 경우와 있는 경우 두 가지 경우로 나눌 수 있다. 가중치가 없는 그래프가중치가 없는 경우 즉 모든 정점간의 이동 비용이 동일한 경우는 BFS 탐색이 가장 간단하다. 이때 BFS의 depth가 총 비용이 된다. 예를 들어 아래와 같은 그래프를 살펴보자.만약 서울에서 출발해서 부산에 도착하는데 각 도시 간 이동 비용이 동일하다면 서울에서 원주, 대구를 찍고 부산에 도착하는게 depth(==비용) 3으로 가장 짧..