[BOJ 1507] 궁금한 민호 (Java)
문제
강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.
도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.
강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.
예를 들어, 예제의 경우에 모든 도시 사이에 강호가 구한 값을 가지는 도로가 존재한다고 해도 된다. 하지만, 이 도로의 개수는 최솟값이 아니다. 예를 들어, 도시 1-2, 2-3, 1-4, 3-4, 4-5, 3-5를 연결하는 도로만 있다고 가정해도, 강호가 구한 모든 쌍의 최솟값을 구할 수 있다. 이 경우 도로의 개수는 6개이고, 모든 도로의 시간의 합은 55이다.
모든 쌍의 도시 사이의 최소 이동 시간이 주어졌을 때, 이 나라에 존재할 수 있는 도로의 개수의 최솟값일 때, 모든 도로의 시간의 합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B가 같은 경우에는 0이 주어지고, 그 외의 경우에 필요한 시간은 2500보다 작거나 같은 자연수이다.
출력
첫째 줄에 도로 개수가 최소일 때, 모든 도로의 시간의 합을 출력한다. 불가능한 경우에는 -1을 출력한다.
접근 방법
-
이미 한 정점 A 에서 다른 정점 B로의 최단 거리를 가지고 있는 경우에서 시작합니다. 즉, 플로이드-와샬 알고리즘으로 이미 최단거리를 구한 상태입니다.
-
우리가 구해야하는 '최소 개수의 도로와 그 시간의 합'은 원본 그래프에서 플로이드 와샬에 쓰이지 않는 도로를 모두 제외하고 남은 값입니다. 하지만 풀이하기에는 어려워 보입니다.
-
생각을 바꾸어서 현재 주어진 그래프에서 플로이드 와샬 알고리즘을 진행해 봅시다. 현재 주어진 그래프는 이미 최단 거리를 가지지만 이 중에서 또한 graph[i][j] = graph[i][k] + graph[k][j] 인 순간이 있다는 것입니다.
-
이를 통해 유추 할 수 있는 것은 우리에겐 3번과 같은 경우는 필요하지 않다는 겁니다. 왜냐하면 오른쪽 항의 graph[i][k] + graph[k][j] 가 있다면 graph[i][j]를 갈 수 있기 때문이죠!
-
위의 논리에 따라서 주어진 그래프에서 플로이드 와샬을 진행하며 3번을 만족하는 경우를 모두 제거해 줍니다.
-
이제 그래프를 돌며 각 값들을 더해준 뒤 2로 나누어 주면 우리가 찾는 최소 개수의 도로의 모든 도로의 시간의 합을 구할 수 있습니다.
⚠️주의할 점⚠️
- 플로이드-워셜 알고리즘을 진행할 때 i == j or j == k or i == k 인 경우는 알고리즘을 진행해서는 안됩니다.
- graph[i][j] > graph[i][k] + graph[k][j] 인 경우는 -1을 출력해 줘야 합니다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class CuriousMinho {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] original = new int[n][n];
int[][] copy = new int[n][n];
for (int i = 0; i < n; i++) {
String[] input = br.readLine().split(" ");
for (int j = 0; j < n; j++) {
original[i][j] = Integer.parseInt(input[j]);
copy[i][j] = original[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (i == j || j == k || i == k) {
continue;
}
if (original[j][k] == original[j][i] + original[i][k]) {
copy[j][k] = 0;
}
if (original[j][k] > original[j][i] + original[i][k]) {
System.out.println(-1);
System.exit(0);
}
}
}
}
int result = 0;
for (int[] ints : copy) {
for (int i : ints) {
result += i;
}
}
System.out.println(result / 2);
}
}
결과
Author And Source
이 문제에 관하여([BOJ 1507] 궁금한 민호 (Java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wotj7687/BOJ-1507-궁금한-민호-Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)