C++ 코딩테스트 강좌, 플로이드-워셜

알고리즘 문제 해결을 위한 강좌에 오신 것을 환영합니다. 오늘의 주제는 ‘플로이드-워셜 알고리즘’입니다.
이 알고리즘은 모든 쌍의 최단 경로를 찾는 데 사용됩니다. 즉, 그래프 내의 모든 노드 쌍 간의 최단 경로를 구하는 데 유용합니다.
이 알고리즘은 특히 중간에 다른 노드를 경유할 수 있는 경우에 유용합니다.
이 글을 통해 문제를 해결하는 과정을 깊이 있게 알아보겠습니다.

문제 설명

주어진 N개의 노드와 M개의 간선으로 이루어진 방향 그래프가 있습니다.
각 간선은 두 노드 간의 거리(비용)를 나타냅니다.
모든 노드 쌍에 대해 최단 거리를 구하는 프로그램을 작성하세요.

입력:

첫 번째 줄에 노드의 개수 N과 간선의 개수 M이 주어진다.
다음 M줄에는 간선의 정보가 주어진다. 각 줄은 u v w로 주어지며, 이는 노드 u에서 노드 v까지 가는 간선의 가중치 w를 나타낸다.

출력:

N개의 노드 간의 최단 경로를 NxN 행렬 형태로 출력한다. 만약 두 노드 간에 경로가 없다면 INF로 출력한다.

입력 예시

출력 예시

0 3 4 5
INF 0 1 2
INF INF 0 2
7 INF INF 0

알고리즘 설명

플로이드-워셜 알고리즘은 동적 프로그래밍을 사용하여 모든 쌍의 최단 경로를 계산합니다.
이 알고리즘의 핵심 아이디어는 다음과 같습니다:

초기 상태로 각 노드 간의 거리를 설정합니다. 직접 연결된 노드는 그 간선의 가중치로 설정하고, 연결되지 않은 노드는 INF로 설정합니다.
각 노드 k를 중간 노드로 사용하여, 모든 노드 i에서 노드 j로 가는 최단 경로를 갱신합니다.
즉, dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])를 사용합니다.
이 과정을 K번 반복하여 모든 쌍의 최단 경로를 찾습니다.

C++ 코드 구현

이제 위의 알고리즘을 C++로 구현해 보겠습니다:

#include 
#include 
#include 
using namespace std;

const int INF = INT_MAX;
const int MAX = 100;

int main() {
    int N, M;
    cin >> N >> M;
    
    vector> dist(MAX, vector(MAX, INF));

    // 초기화
    for (int i = 1; i <= N; i++) {
        dist[i][i] = 0;
    }

    // 간선 정보 입력
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w); // 여러 간선일 경우 최솟값 선택
    }

    // 플로이드-워셜 알고리즘
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    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 << "INF ";
            else cout << dist[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

코드 설명

위의 코드는 다음과 같은 단계로 구성되어 있습니다:

변수 선언: 노드와 간선의 개수를 입력받기 위해 int N, M; 변수를 선언합니다.
인피니티 값을 위해 const int INF = INT_MAX;를 사용합니다.
거리 배열 초기화: 크기가 100인 2차원 벡터 dist를 INF로 초기화합니다.
자기 자신과의 거리는 0으로 setting합니다.
간선 정보 입력: M개의 간선에 대한 정보를 입력받고
dist[u][v]를 적절하게 업데이트합니다.
최단 경로 업데이트: 플로이드-워셜 알고리즘의 핵심인 3중 루프를 통해
중간 노드 k를 사용하여 최단 경로를 업데이트합니다.
결과 출력: 최단 경로 행렬을 출력합니다.
경로가 없는 경우 INF로 출력합니다.

결론

플로이드-워셜 알고리즘은 모든 쌍의 최단 경로를 찾는 강력한 도구입니다.
이 알고리즘은 그래프의 모든 노드 연결 상태를 고려하여 최적의 경로를 찾기 때문에,
특히 다양한 노드 간의 최단 경로를 필요로 하는 여러 상황에서 유용하게 활용됩니다.
코딩 테스트와 같은 알고리즘 문제 풀이에 있어 좋은 연습이 될 것입니다. 알고리즘을 공부하여 성공적인 코딩 테스트를 준비하시기 바랍니다!

추가 자료

더 많은 알고리즘 및 문제를 풀어보고 싶으시다면 아래의 자료들을 참고하시기 바랍니다: