자바 코딩테스트 강좌, 플로이드-워셜

안녕하세요! 이번 강좌에서는 자바 코딩테스트에서 자주 출제되는 플로이드-워셜 알고리즘에 대해 배워보도록 하겠습니다. 플로이드-워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 찾는 데 효율적인 방법입니다. 특히, 그래프의 정점 수가 적은 경우 유용하게 사용됩니다. 이번 글에서는 플로이드-워셜 알고리즘을 적용한 문제를 풀어보며, 그 과정을 자세히 설명하겠습니다.

문제 설명

다음은 플로이드-워셜 알고리즘을 활용한 문제입니다.

문제: 주어진 N개의 도시와 도시 간의 도로 정보를 이용하여, 모든 도시 간의 최단 경로를 구하시오. 
각 도시는 1부터 N까지 번호가 붙어 있으며, 도로는 양방향으로 연결되어 있습니다. 
도로 정보는 다음과 같은 형식으로 주어집니다: 

N  M
x y z 

여기서 N은 도시의 수, M은 도로의 수, x는 도로의 한 쪽 도시, y는 도로의 다른 쪽 도시, z는 두 도시 간의 거리입니다. 
자신과의 거리(예: 1번 도시에서 1번 도시까지의 거리)는 항상 0으로 설정되어 있습니다. 
두 도시 간의 직접적인 도로가 여러 개 있을 경우, 거리 값이 가장 작은 도로 정보만을 고려합니다.

입력 예시:
4 7
1 2 4
1 3 2
2 3 5
2 4 10
3 4 3
1 4 8
3 1 3

출력 예시:
0 2 3 5
2 0 5 3
3 5 0 3
5 3 3 0

문제 풀이 과정

이제 이 문제를 해결하기 위해 플로이드-워셜 알고리즘을 구현해 보겠습니다. 다음은 알고리즘을 단계별로 설명한 것입니다.

1. 데이터 구조 설정

먼저, 모든 도시 간의 거리 정보를 저장할 2차원 배열을 설정합니다. N개의 도시가 있으므로 배열의 크기는 dist[N + 1][N + 1]으로 합니다. 배열의 모든 요소는 초기값으로 무한대(Integer.MAX_VALUE)로 설정합니다. 그러나 각 도시에서 자신까지의 거리는 0으로 설정합니다.

int[][] dist = new int[N + 1][N + 1];

for (int i = 1; i <= N; i++) {
    Arrays.fill(dist[i], Integer.MAX_VALUE);
    dist[i][i] = 0;
}

2. 도로 정보를 입력받아 거리 배열 초기화

입력받은 도로 정보를 통해 각 도시 간의 거리 정보를 설정합니다. 만약 두 도시 간에 여러 개의 도로가 주어진 경우, 거리 배열에는 가장 짧은 거리만 저장합니다.

for (int i = 0; i < M; i++) {
    int x = sc.nextInt();
    int y = sc.nextInt();
    int z = sc.nextInt();
    dist[x][y] = Math.min(dist[x][y], z);
    dist[y][x] = Math.min(dist[y][x], z);
}

3. 플로이드-워셜 알고리즘 구현

플로이드-워셜 알고리즘의 핵심은 삼중 루프를 통해 모든 짝의 최단 거리를 반복적으로 업데이트하는 것입니다. 아래는 플로이드-워셜 알고리즘의 구현 코드입니다.

for (int k = 1; k <= N; k++) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (dist[i][j] > dist[i][k] + dist[k][j]) {
                dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

4. 결과 출력

마지막으로 모든 도시 간의 최단 경로를 출력합니다. 1번 도시부터 N번 도시까지의 거리를 차례대로 출력합니다.

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
        if (dist[i][j] == Integer.MAX_VALUE) {
            System.out.print("INF ");
        } else {
            System.out.print(dist[i][j] + " ");
        }
    }
    System.out.println();
}

전체 코드

이제 위의 모든 과정을 하나의 자바 프로그램으로 통합해 보겠습니다. 아래는 문제를 해결하기 위한 전체 자바 코드입니다.

import java.util.Arrays;
import java.util.Scanner;

public class FloydWarshall {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 도시의 수
        int M = sc.nextInt(); // 도로의 수

        int[][] dist = new int[N + 1][N + 1];

        // 초기화
        for (int i = 1; i <= N; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
            dist[i][i] = 0; // 자기 자신과의 거리는 0
        }

        // 도로 정보 입력
        for (int i = 0; i < M; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            dist[x][y] = Math.min(dist[x][y], z);
            dist[y][x] = Math.min(dist[y][x], z);
        }

        // 플로이드-워셜 알고리즘
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (dist[i][j] > dist[i][k] + dist[k][j]) {
                        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] == Integer.MAX_VALUE) {
                    System.out.print("INF ");
                } else {
                    System.out.print(dist[i][j] + " ");
                }
            }
            System.out.println();
        }
    }
}

정리

이번 강좌에서는 플로이드-워셜 알고리즘을 이용하여 도시 간의 최단 경로를 구하는 문제를 해결해 보았습니다. 이 알고리즘은 모든 쌍의 최단 경로를 구하는 데 유용하게 사용할 수 있으며, 코드의 구조와 로직을 이해하는 데 큰 도움이 되었을 것입니다. 실제 코딩테스트에서는 이러한 알고리즘을 활용하여 효율적인 문제 해결 능력을 키우는 것이 중요합니다.

앞으로도 알릴루야 코딩테스트 강좌에서 다양한 알고리즘을 소개하겠습니다. 감사합니다!