코딩테스트
최단거리류 알고리즘에 대해서(다익스트라,벨만포드,플로이드 등등)
많은 문제들이 최소 비용, 최단거리 등에 집착한다. 하지만 막상 수많은 최단거리, 최소 비용에 대한 문제들을 보면 어떤 알고리즘을 써서 풀어야하지...? 하는 생각이 들고 생각나는대로 문제를 풀면 시간초과 혹은 오답이 나오면 멘붕이 오곤한다.. 이번 글에선 "최단 거리" 에 대해서와, 언제, 어떤걸 써야하는지에 대해 간략하게 정리해 보겠다. 디테일한 설명전 간단한 요약을 먼저 하자면 bfs: 간선에 가중치가 없다(단위길이) , 즉 비용이 아닌 거치는 횟수가 요구될 때. 다익스트라: 특정 시작점 모든 지점 간의 최단거리 플로이드와샬: 모든 시작점 모든 지점 간의 최단거리 벨만포드: 최단거리에서 음수 간선, 등으로 인하여 계속해서 최단거리를 줄여나가는지 "감지" 해야하는 경우 정도로 요약할 수있다. 1)가중..
