백준 온라인 저지(Baekjoon Online Judge) - 11404 : 플로이드

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

11404번: 플로이드

 

#include <iostream>
#include <vector>
using namespace std;

const int INF = 1e9; // 무한대 값

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> dist(n + 1, vector<int>(n + 1, INF)); // 인접 행렬 생성 및 초기화

    // 자기 자신으로 가는 경로는 0으로 설정
    for (int i = 1; i <= n; i++) {
        dist[i][i] = 0;
    }

    // 버스 정보 입력 및 인접 행렬에 비용 할당
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b], c); // 동일 경로에 대해 여러 개의 버스가 있을 수 있으므로 최소 비용을 할당합니다.
    }

    // 플로이드-와샬 알고리즘을 이용하여 최단 거리를 구합니다.
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    // 최단 거리 출력
    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 << endl;
    }

    return 0;
}

백준 11404번 문제는 최단 경로를 계산하는 문제입니다. 이를 플로이드-와샬 알고리즘을 사용하여 해결할 수 있습니다.

먼저, 코드의 첫 부분에서는 필요한 헤더 파일과 namespace를 선언합니다.

다음으로, INF라는 변수에 무한대 값을 저장합니다. 이 값은 경로가 없는 경우를 표현하기 위해 사용됩니다.

주어진 도시의 개수 n과 버스의 개수 m을 입력받습니다.

dist라는 2차원 벡터를 생성하여 인접 행렬을 표현합니다. 모든 요소를 INF로 초기화합니다.

자기 자신으로 가는 경로는 항상 0이므로, 인접 행렬의 대각선 요소를 0으로 설정합니다.

이후, m개의 버스 정보를 입력받고, 인접 행렬에 해당 비용을 할당합니다. 동일한 경로에 여러 개의 버스가 있을 수 있으므로 최소 비용을 할당합니다.

이제 플로이드-와샬 알고리즘을 사용하여 최단 거리를 계산합니다. 중간 정점을 거쳐서 가는 경우와 직접 가는 경우 중 더 작은 값을 선택하여 최단 거리를 갱신합니다. 이 과정을 모든 정점 쌍에 대해 반복합니다.

최단 거리 계산이 완료되면, 결과를 출력합니다. 인접 행렬의 각 요소를 순회하면서 최단 거리를 출력합니다. 만약 경로가 없는 경우 INF로 설정되어 있으므로, 해당 경우에는 0을 출력합니다.

이렇게 작성된 코드는 주어진 도시와 버스 정보를 기반으로 플로이드-와샬 알고리즘을 수행하여 모든 도시 쌍 사이의 최단 거리를 계산하고 출력합니다.

 

* 해당 게시물은 ChatGPT를 참고하여 작성되었음을 알립니다.