7주차(최단경로) - [C++]백준11404 플로이드

28 Apr 2022 in Study on Algorithm

백준11404 플로이드 링크

문제

예제 입력

---

코드

#include<iostream>
#define INF 987654321
using namespace std;

int n, m;
int graph[101][101];

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); //cin 실행속도 향상

    cin >> n;
    cin >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            else graph[i][j] = INF;
        }
    }

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (graph[a][b] > c) graph[a][b] = c;
    }

    // 플로이드 알고리즘
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (graph[i][j] == INF) cout << 0 << ' ';
            else cout << graph[i][j] << ' ';
        }
        cout << '\n';
    }
}

설명

이 문제는 플로이드 알고리즘의 기본적인 개념으로 각 도시에 대한 최단 경로를 구하는 것입니다. 먼저 경로에 대한 정보를 저장할 배열을 선언하고 초기화합니다. 같은 도시로 가는 경로는 없기 때문에 넘어가고 나머지는 아직 길이 정해지지 않았으니 INF(무한대)로 표현했습니다. 이제 경로를 입력 받아 플로이드 알고리즘으로 최단 경로를 찾는데, 단순히 1 => 2로 가는 것뿐만 아니라 1 => 3 => 2등으로 거쳐가는 것을 찾아 최종적으로 1 => 2로 가는 최소 경로를 구합니다. 그리고 이것을 각 도시간에 적용하며 확인할때 처음 초기화했던 INF가 남아 있다면 그곳으로 갈 수 있는 경로는 없으니 0으로 출력합니다.

---

결과