최소 비용 문제를 어떻게 풀 것인가?

 

그래프 문제가 나왔을 때 어떤 자료구조, 알고리즘을 사용해야 할 지 감이 안 잡히는 경우가 많다.

그럴 때 참고하면 좋을 것 같다.

 

1. BFS
   
   1. Queue 사용
   2. 출발지 -> 목적지 사이의 최소 비용 구하기
   3. 가중치가 없는 그래프 일 때
2. Dijkstra
   1. Priority Queue 사용
   2. 출발지 -> 모든 정점의 최소 비용 구하기
   3. 가중치가 음수일 수 없다.
3. Floyd-W
   1. DP 사용
   2. 모든 정점 -> 모든 정점의 최소 비용 구하기
   3. 가중치 상관 없음