공부 기록

그래프에서 사이클의 길이 중 최소 길이를 찾는 문제이다.

d[i][i]를 무한대로 초기화해 준 뒤 플로이드 알고리즘을 적용하면 i->i로 가는 어떠한 경로 중 최소 길이를 얻을 수 있다.

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int mat[][] = new int[n + 1][n + 1];

		for (int i = 1; i <= n; i++) {
			Arrays.fill(mat[i], Integer.MAX_VALUE);
		}
		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int cost = in.nextInt();
			mat[start][end] = Math.min(mat[start][end], cost);
		}

		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (mat[i][k] != Integer.MAX_VALUE && mat[k][j] != Integer.MAX_VALUE) {
						mat[i][j] = Math.min(mat[i][j], mat[i][k] + mat[k][j]);
					}
				}
			}
		}

		int min = mat[1][1];
		for (int i = 2; i <= n; i++) {
			min = Math.min(min, mat[i][i]);
		}

		if (min == Integer.MAX_VALUE) {
			min = -1;
		}
		System.out.println(min);
	}
}

플로이드 알고리즘의 결과가 주어졌을 때,

가능한 경우의 그래프의 최소 간선 수를 구하고, 모든 도로의 cost 합을 구하는 문제이다.

원래 플로이드 알고리즘은

• i->j로 가는 비용이 x보다 클 때, i->k->j로 가는 비용이 x이면 i->j로 가는 도로의 cost를 x로 바꿔준다

이 것을 반대로 적용해보면

• i->j로 가는 비용이 x일 때, i->k->j로 가는 비용이 x이면 i->j로 가는 도로는 필요없다.

입력이 이미 최단경로가 주어져있는데 다시 최단경로를 계산해보니 더 짧아진 경우는 입력이 모순이 되므로 -1을 출력하도록 했다.

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int mat[][] = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				mat[i][j] = in.nextInt();
			}
		}

		int ans = 0;
		boolean isEdge[][] = new boolean[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			Arrays.fill(isEdge[i], true);
		}

		Floyd: 
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				if (k == i) {
					continue;
				}
				for (int j = 1; j <= n; j++) {
					if (k == j || i == j) {
						continue;
					}

					if (mat[i][j] > mat[i][k] + mat[k][j]) {
						ans = -1;
						break Floyd;
					}

					if (mat[i][j] == mat[i][k] + mat[k][j]) {
						isEdge[i][j] = false;
						isEdge[j][i] = false;
					}
				}
			}
		}

		if (ans != -1) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (isEdge[i][j]) {
						ans += mat[i][j];
					}
				}
			}
			ans /= 2; // 양방향이므로 2로 나눠준다.
		}
		System.out.println(ans);
	}
}

플로이드 알고리즘: 모든 쌍의 최단 경로를 구하는 알고리즘

c.f. 벨만 포드/다익스트라 알고리즘: 시작점이 1개일 때

이 문제는 플로이드 알고리즘을 써서 풀 수 있다.

그런데, 도시 i에서 도시 j로 가는 최소 비용에 포함되어 있는 도시의 개수 K를 출력해야 하기때문에

그동안 지나왔던 경로도 저장해야 한다.

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int mat[][] = new int[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			Arrays.fill(mat[i], 1000000);
			mat[i][i] = 0;
		}
		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int cost = in.nextInt();
			mat[start][end] = Math.min(mat[start][end], cost);
		}

		int route[][] = new int[n + 1][n + 1];
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (mat[i][j] > mat[i][k] + mat[k][j]) {
						route[i][j] = k; // i~j를 갈 때 k를 거친다
						mat[i][j] = mat[i][k] + mat[k][j];
					}
				}
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				System.out.print(mat[i][j] + " ");
			}
			System.out.println();
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) {
					System.out.println("0");
				} else {
					LinkedList<Integer> list = new LinkedList<Integer>();
					routeList(i, j, route, list);
					System.out.print(list.size() + " ");
					for (int k = 0; k < list.size(); k++) {
						System.out.print(list.get(k) + " ");
					}
					System.out.println();
				}
			}
		}
	}

	public static void routeList(int start, int end, int route[][], LinkedList<Integer> list) {
		if (route[start][end] == 0) { // i~j를 갈 때 거치는 점이 없을
			list.add(start);
			if (start != end) {
				list.add(end);
			}
		} else {
			int middle = route[start][end]; // i~j를 갈 때 경유
			routeList(start, middle, route, list);
			list.removeLast(); // 중복 제거
			routeList(middle, end, route, list);
		}
	}
}

그동안 지나왔던 경로를 저장할 때에는 route[i][j]에 i와 j를 지날 때 경유한 점을 저장하도록 한다.

즉, route[i][j]에는 i->j 간선이 원래 어디를 가르켰는지 저장한다.

경유했던 점들의 리스트를 가져올 때에는 routeList에서 list에 하나씩 넣는데

routeList(start, middle, route, list)와 routeList(middle, end, route, list)에서 middle 부분이 list에 두번 중복되어 들어가므로 한 번 제거해줘야한다.