[백준/BOJ] 11404번: 플로이드 ( 플로이드-워셜 알고리즘) - C++ 문제 풀이

문제 설명

 

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

 

풀이

이 문제는 모든 도시에서 다른 도시에 도달하는 최단 거리를 출력하는 문제입니다.

여기서는 플로이드-워셜( Floyd-warshall ) 알고리즘을 사용합니다.

 

다익스트라( Dijkstra ) 알고리즘이나 벨만-포드( Bellman-Ford ) 알고리즘이 한 도시에서 다른 도시까지의 최단 거리를 구하는 데 사용하는 알고리즘이라면, 플로이드-워셜 알고리즘은 모든 도시에서 다른 도시까지의 최단 거리를 한 번에 구하는 알고리즘입니다.

 

플로이드-워셜 알고리즘에 관한 내용은 여기에서 볼 수 있습니다.

[C++] 최단 거리를 구하는 플로이드-워셜 알고리즘

 

이 알고리즘은 인접 배열에 최단 거리를 저장합니다.

먼저, 주어진 그래프에서 인접 배열을 구성합니다.

#include <iostream>
using namespace std;

#define SIZE    100
#define MAX_DIST    10000001    // 임의의 큰 거리
int D[SIZE+1][SIZE+1];    // 최단 거리를 저장할 인접 배열

int main(){

    int n, m;
    cin >> n;	// 정점의 개수
    cin >> m;	// 간선의 개수

    // 초기화
    for( int i = 1; i <= n; i++){
        for( int j = 1; j<= n; j++){
            if ( i == j)
                D[i][j] = 0;	// 같은 정점까지 가는 최단 거리는 0
            else
                D[i][j] = MAX_DIST;
        }
    }
    
    // 인접 배열 구성
    int a, b, c;
    for( int i = 0 ; i < m ; i++){
        cin >> a >> b >> c;

        if ( D[a][b] > c) // 거리가 다른 경로가 1개 이상이 경우를 고려
            D[a][b] = c;	
    }

    floyd_warshall(n);	// 플로이드-워셜 알고리즘 적용

    // 계산된 최단 거리를 출력
    for( int i = 1; i <= n; i++){
        for( int j = 1; j<= n; j++){
            if ( D[i][j] == MAX_DIST)
                D[i][j] = 0;	// 도달하지 못한 정점은 0으로 출력

            cout << D[i][j] << " ";
        }

        cout << endl;
    }

    return 0;
}

 

이제,  주어진 인접 배열로부터, 배열의 나머지 부분을 최단 거리로 채웁니다.

void floyd_warshall(int V){

    for( int B = 1; B <= V; B++){
        for( int A = 1; A <= V; A++){
            for( int C = 1; C <= V; C++){
                
                D[A][C] = min( D[A][C], D[A][B] + D[B][C]);
            }
        }
    }
}

이 함수가 종료되면 배열 D에 모든 정점 간의 최단 거리가 저장됩니다.

 

 

소스 코드

#include <iostream>
using namespace std;

#define SIZE    100
#define MAX_DIST    10000001    // 임의의 큰 거리
int D[SIZE+1][SIZE+1];    // 인접 배열

void floyd_warshall(int V){

    for( int B = 1; B <= V; B++){
        for( int A = 1; A <= V; A++){
            for( int C = 1; C <= V; C++){
                
                D[A][C] = min( D[A][C], D[A][B] + D[B][C]);
            }
        }
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    // 초기화
    for( int i = 1; i <= n; i++){
        for( int j = 1; j<= n; j++){
            if ( i == j)
                D[i][j] = 0;
            else
                D[i][j] = MAX_DIST;
        }
    }
    
    int a, b, c;
    for( int i = 0 ; i < m ; i++){
        cin >> a >> b >> c;

        if ( D[a][b] > c)
            D[a][b] = c;
    }

    floyd_warshall(n);

    for( int i = 1; i <= n; i++){
        for( int j = 1; j<= n; j++){
            if ( D[i][j] == MAX_DIST)
                D[i][j] = 0;

            cout << D[i][j] << " ";
        }

        cout << endl;
    }

    return 0;
}