📌 풀이 과정
이 문제는 플로이드-와샬 알고리즘을 사용하여 도시 간의 최단 거리를 이미 구해놓은 상태에서, 그 정보를 바탕으로 실제 최소 도로의 개수와 총 도로 시간의 합을 계산하는 문제이다.
문제를 해결하는 핵심은 플로이드-와샬 알고리즘을 역으로 이용하여 불필요한 도로를 제거하고, 필수적인 도로만 남기는 것이다.
그렇다면 플로이드 와샬이란 뭘까?
💡 플로이드 와샬(Floyd Warshall)
모든 정점에서 모든 정점까지의 최단 경로를 구하는 알고리즘이다.
두 정점 i와 j 사이에 직통 경로가 있다고 해도, 중간에 다른 도시 k를 거쳐 가는 경로가 더 짧으면 그 경로를 선택한다.
즉, dist[i][j]를 i에서 j로 가는 현재 최단 거리라고 할 때
만약 dist[i][j] > dist[i][k] + dist[k][j]라면, i에서 k를 거쳐 j로 가는 경로가 더 짧다는 의미이다.
이 조건을 만족하는 경우, i에서 j로 직접 가는 경로는 의미가 없기 때문에 제거할 수 있다.
💡 문제에서 요구하는 내용
이 문제는 플로이드-와샬 알고리즘을 이용해서 구한 도시 간 최단 거리 표를 역으로 분석하여 직접 연결된 도로의 개수와 도로 시간의 합을 구하라는 것이다.
💡 역으로 생각하기 - 불필요한 도로 제거
문제에서 주어진 최단 거리 정보를 바탕으로
실제로 필요한 도로만 남기기 위해 아래와 같이 할 수 있다.
1. 중간 경유 도시가 있는 경우 직접 연결된 도로 제거
- 만약 도시
i와 도시j가 도시k를 경유하여 더 짧은 경로로 갈 수 있다면,i에서j로 가는 직접 연결된 도로는 불필요하다. - 이를 플로이드-와샬 알고리즘을 통해 다시 확인한다.
- 만약
dist[i][j] > dist[i][k] + dist[k][j]라는 조건을 충족하면, 이는 원래 최단 거리 정보가 모순되었으므로, -1을 출력하고 종료한다.
2. 직접 연결된 도로들의 시간 합 계산
플로이드-와샬 알고리즘을 다시 실행하면서, 직접 연결된 도로만 남긴 후, 그 도로들의 시간을 더한다.
✨ 제출 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* 1507.궁금한 민호
* 메모리 : 14148 KB
* 시간 : 104 ms
*/
public class Main {
static int N;
static int[][] dist;
static int[][] original;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
dist = new int[N][N];
original = new int[N][N];
// 입력 받기
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
dist[i][j] = Integer.parseInt(st.nextToken());
original[i][j] = dist[i][j]; // 원본 배열 저장
}
}
// 플로이드-와샬을 통해 불필요한 도로를 제거
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// i == j 인 경우는 거리가 0이므로 건너뛴다.
if (i == j || i == k || j == k) continue;
// i에서 j로 가는 거리가 i에서 k를 거쳐 j로 가는 것보다 크면 모순이 발생
if (dist[i][j] > dist[i][k] + dist[k][j]) {
System.out.println(-1);
return;
}
// i에서 j로 가는 거리가 i에서 k를 거쳐 j로 가는 것과 동일하면 직접 연결 도로가 아니므로 제거
if (dist[i][j] == dist[i][k] + dist[k][j]) {
original[i][j] = 0; // 중간 경유지가 있는 도로는 직접 연결 도로가 아님
}
}
}
}
// 도로 시간 합 계산
int roadSum = 0;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
roadSum += original[i][j];
}
}
System.out.println(roadSum);
}
}References
항상 궁금해하기