플로이드-워셜(Floyd-warshall) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 아래와 같습니다.
| 기능 | 특징 | 시간 복잡도 (V: 노드 수) |
| 모든 노드 간에 최단 경로 탐색 | ▪️ 음수 가중치 에지가 있어도 수행할 수 있음. ▪️ 동적 계획법의 원리를 이용해서 알고리즘에 접근 |
O(V³) |
플로이드-워셜의 핵심 이론
플로이드-워셜 알고리즘을 도출하는 가장 핵심적인 원리는 A 노드에서 B 노드까지의 최단 경로 'X'를 구했다고 가정했을 때 그 최단 경로 'X' 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것입니다.
위에 빨간색 경로가 노드 1 에서 노드 5로 가는 최단경로라고 합시다. 그렇다면 1 -> 4 최단 경로와 4 -> 5 의 최단 경로도 빨간색 경로 안에 있을 수 밖에 없습니다.
즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이루어진다는 의미가 됩니다.
플로이드-워셜 점화식
D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])
플로이드-워셜 알고리즘 구현 방법
1, 배열을 선언하고 초기화
D[S][E] 는 노드 S 에서 E 까지의 최단 거리를 저장하는 배열입니다.
S == E 이면 자기 자신에게 가는 데 걸리는 최단 경로값이므로 0 입니다.
2. 최단 거리 배열에 그래프 데이터 저장
출발 노드 S, 도착 노드 E, 해당 에지의 가중치를 W 라고 했을 때 D[S][E] = W 로 에지의 정보를 배열에 입력합니다.
플로이드-워셜 알고리즘은 그래프를 인접 행렬로 표현한 것입니다.
3. 점화식으로 배열 업데이트
기존에 구했던 점화식을 3중 for 문의 형태로 반복하면서 배열의 값을 업데이트합니다.
플로이드-워셜 알고리즘 로직
for 경유지 K 에 대해서 (1 ~ N 까지)
for 출발 노드 S 에 대해 (1 ~ N 까지)
for 도착 노드 E 에 대해 (1 ~ N 까지)
D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])여기서 경유지 K 가 먼저 나와야 하는 것이 중요합니다!
완성된 배열은 모든 노드 간의 최단 거리를 알려줍니다. D[1][5] = 6 은 노드 1에서 노드 5 까지의 최단 거리가 6이라는 것을 의미합니다.
플로이드-워셜 알고리즘은 모든 노드 간의 최단 거리를 확인해주기 때문에 시간복잡도가 O(V³) 으로 빠르지 않습니다.
플로이드-워셜 알고리즘을 사용해야 하는 문제가 나오면 일반적으로 노드의 개수의 범위가 다른 그래프에 비해서 더 적습니다.
백준 11404 플로이드
https://www.acmicpc.net/problem/11404
11404번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
1. 문제 분석
그래프에서 시작점을 정하지 않고 모든 노드와 관련된 최소 경로를 구하는 알고리즘이 플로이드-워셜 알고리즘입니다.
도시의 최대 개수가 100개로 매우 작은 편이므로 O(N³) 시간 복잡도의 플로이드-워셜 알고리즘으로 해결합니다.
2. 손으로 풀기
a. 버스 비용 정보를 인접 행렬에 저장.
b. 플로이드-워셜 알고리즘 수행. 점화식을 사용한 3중 for 문으로 모든 중간 경로를 탐색.
for 경유지 K 에 대해서 (1 ~ N 까지)
for 출발 노드 S 에 대해 (1 ~ N 까지)
for 도착 노드 E 에 대해 (1 ~ N 까지)
D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])c. 인접 행렬을 조건에 맞게 출력.
3. 슈도코드
N: 노드(도시) 개수
M: 에지(노선) 개수
graph[][] 에지 정보 저장
graph 을 0 과 ∞ 로 초기화. ∞ 는 충분히 큰 수로
// 플로이드 워셜 알고리즘
for (중간경로 m 가 1 ~ n)
for(출발 도시 s 가 1 ~ n)
for(도착 도시 e 가 1 ~ n)
D[s][e] = Math.min(graph[s][e], graph[s][m] + graph[m][e])
// graph 출력
graph[i][j] == ∞ 이면 0 출력.
아니면 graph[i][j] 출력.4. 코드
public class BaekJun11404Self {
static BufferedWriter bw;
static int N;
static long[][] graph;
public static void main(String[] args) throws IOException {
input();
// floyd-warshall
floydWarshall();
// 출력
output();
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
graph = new long[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
Arrays.fill(graph[i], 9_999_999);
graph[i][i] = 0;
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
graph[s][e] = Math.min(graph[s][e], w);
}
br.close();
}
private static void floydWarshall() {
for (int m = 1; m <= N; m++) {
for (int s = 1; s <= N; s++) {
for (int e = 1; e <= N; e++) {
graph[s][e] = Math.min(graph[s][e], graph[s][m] + graph[m][e]);
}
}
}
}
private static void output() throws IOException {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
long tmp = graph[i][j];
if (tmp == 9_999_999) {
bw.write(0 + " ");
} else {
bw.write(tmp + " ");
}
}
bw.write("\n");
}
bw.flush();
bw.close();
}
}여기서 주의할 점은 ∞ 을 Long.MAX_VALUE 로 하면 안 된다는 것입니다.
플로이드 워셜 알고리즘에서 Math.min 함수를 수행할 때 Long.MAX_VALUE 끼리 더하게 되면 컴퓨터에서 숫자형을 저장하는 방식에 따라 음수가 될 수 있기 때문에 서로 더했을 때 Long 의 양수 범위를 초과하지 않는 값으로 설정해 주어야합니다.
백준 11403 경로 찾기
https://www.acmicpc.net/problem/11403
11403번: 경로 찾기
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
1. 문제 분석
마찬가지로 노드 수가 굉장히 적고 시간 제한이 여유 있습니다.
모든 노드 쌍에 관해 경로가 있는지 여부를 확인하는 방법은 플로이드-워셜 알고리즘을 사용하면 됩니다. 이전 문제에서 최단 거리를 업데이트하는 부분만 조금 수정해주면 될 것 같네요.
2. 손으로 풀기
a. 그래프(인접행렬) 초기화
b. 플로이드 워셜 알고리즘 수행
중간 노드 m 에 대해서 어떤 출발 노드 s 에서 m 으로 가는 길이 존재(D[s][m] ==1)하고 m 에서 어떤 도착 노드 e 로 가는 길이 존 (D[m][e] == 1)하면 s 에서 e 로 가는 길이 존재한다는 의미입니다.
플로이드-워셜 알고리즘을 사용하여 노드 1 부터 N 까지 모든 노드를 중간노드로 간주하고 출발 노드와 도착 노드를 1 부터 N 까지 변경해 가면서 검사하면 됩니다.
if(D[s][m] == 1 && D[m][e] == 1) -> D[s][e] = 1;
c. 인접행렬 출력
3. 슈도코드
N: 노드 개수
graph[][] : 에지 인접 행렬
for(1 ~ N){
에지 초기화
}
// floyd-warshall
for(중간 노드 m 이 1 ~ N) {
for( 시작 노드 s 가 1 ~ N) {
for( 도착 노드 e 가 1 ~ N) {
if(D[s][m] == 1 && D[m][e] == 1){
D[s][e] = 1;
}
}
}
}
출력4. 코드
public class BaekJun11403 {
static BufferedWriter bw;
static int N;
static int[][] graph;
public static void main(String[] args) throws IOException {
// input
input();
// floyd-warshall
floydWarshall();
// output
output();
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
graph = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
graph[i][j] = Integer.parseInt(st.nextToken());
}
}
br.close();
}
private static void floydWarshall() {
for (int m = 1; m <= N; m++) {
for (int s = 1; s <= N; s++) {
for (int e = 1; e <= N; e++) {
if (graph[s][m] == 1 && graph[m][e] == 1) {
graph[s][e] = 1;
}
}
}
}
}
private static void output() throws IOException {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
bw.write(graph[i][j] + " ");
}
bw.write("\n");
}
bw.flush();
bw.close();
}
}
백준 1389 케빈 베이컨의 6단계 법칙
https://www.acmicpc.net/problem/1389
1389번: 케빈 베이컨의 6단계 법칙
첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻
www.acmicpc.net
1. 문제 분석
BFS 탐색 알고리즘을 이용해도 해결할 수 있는 문제입니다. 하지만 유저의 최대 수가 100 정도로 작고 시간 제한도 1초 이므로 여유있기 때문에 플로이드 워셜 알고리즘을 사용해도 해결할 수 있습니다.
사람들이 직접적인 친구 관계를 맺은 상태를 비용 1로 계산(가중치 1로 인접 행렬에 저장)하여 풀면 됩니다. 구체적인 것은 손으로 풀기에서 설명하겠습니다.
2. 손으로 풀기
a. 먼저 인접 행렬을 생성하고 에지 데이터를 초기화.
b. 점화식을 이용해서 플로이드-워셜 알고리즘을 수행하여 3중 for 문으로 모든 중간 경로를 탐색
c. 케빈 베이컨 수는 플로이드워셜 알고리즘을 통과한 후 graph의 각 행의 합으로 합임. 해당 수 중에서 가장 작은 수를 가진 노드를 출력하면 됨.
3. 슈도코드
N: 노드(유저) 수, M: 에지(친구 관계) 수
graph: 인접 행렬로 그래프 저장
answer: 정답 변수
graph 에 값을 0 과 ∞ 로 설정
graph 에 에지 데이터 초기화
// Floyd-Warshall
for(m: 1 ~ N){
for(s: 1 ~ N){
for(e: 1 ~ N){
점화식
}
}
}
for(i: 1 ~N) {
for(j: 1 ~N) {
if(graph[i][j] != ∞){
graph[0][i] += graph[i][j];
}
}
answer = Math.min(answer, graph[0][i])
}
answer 출력4. 코드
public class BaekJun1389 {
static BufferedWriter bw;
static int N;
static int[][] graph;
static int kevinNum = 9_999;
static int answer = 0;
public static void main(String[] args) throws IOException {
input();
floydWarshall();
checkKevinNum();
System.out.println(answer);
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
graph = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
Arrays.fill(graph[i], 9_9999);
graph[i][0] = 0;
graph[i][i] = 0;
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
graph[A][B] = 1;
graph[B][A] = 1;
}
}
private static void floydWarshall() {
for (int m = 1; m <= N; m++) {
for (int s = 1; s <= N; s++) {
for (int e = 1; e <= N; e++) {
graph[s][e] = Math.min(graph[s][e], graph[s][m] + graph[m][e]);
}
}
}
}
private static void checkKevinNum() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (graph[i][j] != 9_999) {
graph[i][0] += graph[i][j];
}
}
if (kevinNum > graph[i][0]) {
kevinNum = graph[i][0];
answer = i;
}
}
}
}
'Java > 코딩테스트' 카테고리의 다른 글
| [JAVA] 트리 자바 백준 BOJ 11725, 1068 (0) | 2023.08.27 |
|---|---|
| [JAVA] 최소 신장 트리 알고리즘 자바 백준 BOJ 1197, 17472, 1414 (2) | 2023.08.24 |
| 벨만 포드 알고리즘 자바 백준 BOJ 11657, 1219 (0) | 2023.08.18 |
| 우선순위 큐를 이용한 다익스트라 알고리즘 자바 백준 BOJ 1735, 1916, 1854 (0) | 2023.08.17 |
| 위상정렬 자바 백준 BOJ 2252, 1516, 1948 (0) | 2023.08.07 |