[백준] 11404 - 플로이드

11404. 플로이드 풀이

난이도: Gold IV
문제 주소: https://www.acmicpc.net/problem/11404

문제 풀이

이 문제는 제목에서도 나와있듯이 플로이드 알고리즘을 연습해 보기위한 문제이다

for (int i = 0; i < 101; i++) fill(city[i], city[i] + 101, INT_MAX);
while (m--) {
    int a, b, c;
    cin >> a >> b >> c;
    city[a][b] = min(city[a][b], c);
}
for (int i = 1 ; i <= n ; i++)city[i][i] = 0;

처음에는 2차원 배열 city의 모든 값을 INT_MAX로 초기화했다. 버스 노선의 정보를 입력받을 때 주의해야 할 점은 시작 도시와 도착 도시를 연결하는 노선이 하나가 아닐 수 있다는 것이다. 따라서 중복되는 노선이 주어질 경우 min 함수를 사용하여 더 적은 비용만 배열에 저장되도록 처리하고 자기 자신으로 가는 비용은 모두 0으로 설정해 두었다.

for (int k = 1; k <= n; k++) {
    for (int i = 1 ; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (city[i][k] == INT_MAX || city[k][j] == INT_MAX) continue;
            city[i][j] = min(city[i][j], city[i][k] + city[k][j]);
        }
    }
}

 

이후 3중 반복문을 통해 거쳐 가는 도시 k, 출발 도시 i, 도착 도시 j를 순회하며 최단 경로를 계산했다. 여기서 두 경로의 비용을 더하는 과정(city[i][k] + city[k][j])에서 INT_MAX 값끼리 더해져 오버플로우가 발생하는 것을 방지하기 위해 city[i][k]나 city[k][j]가 INT_MAX인 경우에는 continue로 넘어가도록 예외 처리를 추가했다. 거쳐 가는 경로의 비용 합이 기존에 저장된 비용보다 작다면 배열 값을 갱신하는 방식으로 모든 쌍의 최소 비용을 구했다.

결과적으로 출력을 진행할 때 배열의 값이 INT_MAX라면 갈 수 없는 경로이므로 문제 조건에 맞게 0을 출력하고 그렇지 않은 경우에는 갱신된 최소 비용을 출력하도록 마무리했다.

최종 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <climits>

using namespace std;

int city[101][101];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    for (int i = 0; i < 101; i++) fill(city[i], city[i] + 101, INT_MAX);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        city[a][b] = min(city[a][b], c);
    }
    for (int i = 1 ; i <= n ; i++)city[i][i] = 0;
    for (int k = 1; k <= n; k++) {
        for (int i = 1 ; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (city[i][k] == INT_MAX || city[k][j] == INT_MAX) continue;
                city[i][j] = min(city[i][j], city[i][k] + city[k][j]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (city[i][j] == INT_MAX)cout << "0" << " ";
            else cout << city[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}   

---

'Algorithm > 백준' 카테고리의 다른 글

[백준] 5525 - IOIOI  (0)	2026.04.12
[백준] 12015 - 가장 긴 증가하는 부분 수열2  (0)	2026.04.08
[백준] 9663 N－Queen  (0)	2026.04.01
[백준] 10814 - 나이순 정렬  (0)	2026.04.01
[백준] 10942 - 팰린드롬?  (0)	2026.03.23