[C++] 백준 11404 - 플로이드(플로이드 알고리즘)

0. [c++] 백준

https://www.acmicpc.net/problem/11404

1. 풀이

이 문제는 다익스트라 알고리즘을 일반화한 것과 비슷한 풀이과정으로 흘러간다.

모든 경로에 대해 최단거리를 구하는 알고리즘인 플로이드(floyd) 알고리즘을 활용한다.

이 플로이드 알고리즘은 다익스트라(dijkstra) 알고리즘과 진행이 거의 유사한데, 차이점으로 경유점을 잡고 문제가 진행되는 것이다.

기본적인 다익스트라 알고리즘(https://kyunstudio.tistory.com/251, 이전 다익스트라 문제)은 시작점을 변수로 선언하고, 그 점에서 시작하여 뻗어나가는 가지와 같은 형태로 알고리즘이 확장이 된다. 가장 최소거리를 저장해주면서 최종적인 결과를 반환한다.

하지만, 이번 알고리즘은 모든 점에 대해 최단거리를 구해야하기에 시작점, 도착점, 경유점을 미리 선정하고, 모든 경우에 대해 최단거리를 구하는 방향으로 알고리즘을 만들어주자.

방법으로는

(1) 경유, 출발, 도착지를 선택(이를 a,b,c라 하자)

(2) a -> b -> c 의 경로로 가는 거리가 기존의 a -> c 의 거리보다 작은 경우

    a -> c 의 거리를 a -> b -> c의 거리로 바꾸어준다.

(3) 이 방법을 1~N의 모든 경우에 대해 경유하도록 하여 최단거리를 찾아준다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

#include<iostream> #include<vector> #include<queue> #include<cstring>   using namespace std;   const int INF = 1000000007; const int MAX_V = 101;   //dist[a][b] = a에서 b까지 걸리는 최소 비용 int dist[MAX_V][MAX_V];   int N, M;   void floyd() {     for (int iter = 1; iter <= N; iter++) {         for (int here = 1; here <= N; here++) {             for (int there = 1; there <= N; there++) {                 int cost = dist[here][iter] + dist[iter][there];                 if (dist[here][there] > cost)                     dist[here][there] = cost;             }         }     } }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     cin >> N >> M;       for (int i = 1; i <= N; i++)         for (int j = 1; j <= N; j++)             dist[i][j] = INF;       for (int i = 1; i <= N; i++)          dist[i][i] = 0;            int a, b, c;     for (int i = 0; i < M; i++) {         cin >> a >> b >> c;         if (dist[a][b] > c)             dist[a][b] = c;     }       floyd();       for (int i = 1; i <= N; i++) {         for (int j = 1; j <= N; j++) {             if (dist[i][j] == INF)                 cout << 0 << " ";             else                 cout << dist[i][j] << " ";         }         cout << "\n";     }       return 0; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!