백준 11404번 [플로이드](C++)-yes6686- 티스토리

백준 문제 풀이: 11404 [플로이드]

---

문제 링크: https://www.acmicpc.net/problem/11404

문제 설명:

n개의 도시와 도시를 연결하는 m개의 버스가 주어질 때, 모든 도시 간의 최소 비용을 구하는 문제입니다. 주어진 입력은 방향 그래프이며, 간선의 가중치가 존재합니다. 출력은 도시 i에서 도시 j로 이동하는 데 드는 최소 비용을 나타내는 n × n 행렬입니다. 만약 갈 수 없다면 0을 출력합니다.

입력:

• 첫 번째 줄에 도시의 개수 n (2 ≤ n ≤ 100)이 주어집니다.
• 두 번째 줄에 버스의 개수 m (1 ≤ m ≤ 100,000)이 주어집니다.
• 다음 m개의 줄에는 출발 도시, 도착 도시, 비용이 주어집니다.

출력:

• i에서 j로 가는 최소 비용을 나타내는 n × n 행렬을 출력합니다. 갈 수 없는 경우는 0을 출력합니다.

---

문제 해결 코드

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

const int INF = 1e9;
int graph[101][101];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    // 그래프 초기화
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                graph[i][j] = 0;
            } else {
                graph[i][j] = INF;
            }
        }
    }

    // 간선 정보 입력
    for (int i = 0; i < m; i++) {
        int a, b, cost;
        cin >> a >> b >> cost;
        graph[a][b] = min(graph[a][b], cost); // 동일 간선 중 최소 비용 선택
    }

    // 플로이드-워셜 알고리즘
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (graph[i][k] + graph[k][j] < graph[i][j]) {
                    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';
    }

    return 0;
}

예제

입력:
5
14
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
5 1 7
5 2 4
4 5 1

출력:
0 2 3 1 4 
12 0 15 2 5 
8 5 0 1 1 
10 7 13 0 1 
7 4 10 1 0

---

코드 설명

• 그래프 초기화:
  • 자기 자신으로 가는 비용은 0으로 설정하고, 다른 경로는 INF로 초기화합니다.
• 간선 정보 입력:
  • 동일한 출발점과 도착점을 가지는 간선이 여러 개 주어질 수 있으므로 최소 비용만 저장합니다.
• 플로이드-워셜 알고리즘:
  • 모든 정점 i, j에 대해 k를 경유하는 최소 비용을 계산합니다.
  • 경유 비용이 기존 비용보다 작으면 업데이트합니다.
• 결과 출력:
  • 도달 불가능한 경우 0을 출력하고, 가능한 경우 최소 비용을 출력합니다.

시간 복잡도

• 플로이드-워셜 알고리즘의 시간 복잡도는 O(n³)입니다.
• n의 최대값이 100이므로 10⁶번 연산이 가능하며 효율적으로 동작합니다.

---

결과

코드는 모든 정점 간 최단 경로를 정확히 계산하며, 플로이드-워셜 알고리즘을 활용한 효율적인 풀이를 제공합니다. 입력 데이터에 따라 그래프 초기화와 간선 처리 과정을 적절히 구현하였습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!