[BOJ] 11404 플로이드 C++ 문제풀이 & 소스코드

INFO

난이도 : GOLD4

유형 : Graph Folyd Warshall

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

---

SOLVE

플로이드 와샬 알고리즘을 사용해 특정 정점으로부터 모든 정점 사이의 거리의 가중치를 구해주면 되는 간단한 문제이다.

n의 최대 크기는 100이며, Floyd Warshall은 O(N^3) 만큼의 TimeComplexity를 소모하기에 1초 안에 충분히 로직을 수행 가능하다.

 

정점 사이의 간선이 존재하지 않는 경우를 인접행렬에 저장하기 위해 별도의 INF 상수를 정의한다. 

dist 배열에는 정점 사이의 간선 가중치를 저장한다. 

const int INF = 10001000;
int dist[101][101];

 

정점의 수 n (도시의 개수) 과 간선의 개수 m (버스의 개수)를 입력받는다.

    int n, m; // (2<=n<=100),(1<=m<=100,000)
    cin >> n >> m;

 

거리 배열 (dist) 내부의 값을 같은 정점은 0으로 초기화하고 나머지는 모두 INF(무한대)로 초기화한다. 

    // 시작도시 a, 도착도시 b, 비용 c
    // Logic1 : 거리 배열 (dist) 값을 모두 무한대 INF 로 초기화
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dist[i][j] = INF;
            if (i == j) dist[i][j] = 0;
        }
    }

 

버스의 수 만큼 반복하여 시작 도시 정점 (city1)과 도착 도시 정점 (city2) 그리고 필요한 비용 (cost)를 입력받는다. 

단, 문제에서 제시한 조건에 따르면 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다고 하였기에 

기존에 저장된 값과 비교하여 더 적은 가중치를 가지고 있다면 dist 배열 정보를 업데이트하지 않고 continue한다. 

    int city1, city2, cost;
    for (int i = 0; i < m; i++) {
        cin >> city1 >> city2 >> cost;
        if (dist[city1][city2] != INF) {
            if (dist[city1][city2] < cost)
                continue;
        }
        dist[city1][city2] = cost;
    }

 

n번만큼 루프를 돌며 Floyd-Warshall 알고리즘 로직을 수행한다. 

    // logic2 : Floyd-Warshall
    for (int round = 1; round <= n; round++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                dist[i][j] = min(dist[i][j], dist[i][round] + dist[round][j]);
            }
        }
    }

 

마지막으로 dist 배열에 저장된 정보를 출력해주면 된다.

    // logic3 : output
    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';
    }

---

CODE

https://github.com/novvvv/PS/blob/main/BOJ/2025/C%2B%2B/BOJ11404.cpp

PS/BOJ/2025/C++/BOJ11404.cpp at main · novvvv/PS