안녕하세요! 이번 강좌에서는 자바 코딩테스트에서 자주 출제되는 플로이드-워셜 알고리즘에 대해 배워보도록 하겠습니다. 플로이드-워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 찾는 데 효율적인 방법입니다. 특히, 그래프의 정점 수가 적은 경우 유용하게 사용됩니다. 이번 글에서는 플로이드-워셜 알고리즘을 적용한 문제를 풀어보며, 그 과정을 자세히 설명하겠습니다.
문제 설명
다음은 플로이드-워셜 알고리즘을 활용한 문제입니다.
문제: 주어진 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();
}
}
}정리
이번 강좌에서는 플로이드-워셜 알고리즘을 이용하여 도시 간의 최단 경로를 구하는 문제를 해결해 보았습니다. 이 알고리즘은 모든 쌍의 최단 경로를 구하는 데 유용하게 사용할 수 있으며, 코드의 구조와 로직을 이해하는 데 큰 도움이 되었을 것입니다. 실제 코딩테스트에서는 이러한 알고리즘을 활용하여 효율적인 문제 해결 능력을 키우는 것이 중요합니다.
O(N^3)이므로, 그래프의 정점 수가 많을 경우 다른 최단 경로 알고리즘(예: 다익스트라 알고리즘)을 고려하는 것이 좋습니다.
앞으로도 알릴루야 코딩테스트 강좌에서 다양한 알고리즘을 소개하겠습니다. 감사합니다!