728x90
1507 - 궁금한 민호
https://www.acmicpc.net/problem/1507

문제
N개의 도시로 이뤄진 나라/ 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간 존재
도시 A -> B 바로 갈 수 있는 도로 or 다른 도시 거쳐서 갈 수 있음
=> 모든 쌍의 도시에 대해 최소 이동 시간 주어졌을 때, 존재할 수 있는 도로의 개수가 최솟값일 때, 모든 도로의 시간 합?
입력
첫째 줄: 도시 개수 N (1 <= N <= 20)
둘째 줄 ~ N개 줄: 각각 도시 사이에 이동하는데 필요한 시간
(A -> B == B -> A / A와 B가 같은 경우 0 / 그 외 필요한 시간 <= 2500)
출력: 도로 개수 최소일 때, 모든 도로의 시간 합 / 불가능 -> -1
풀이
입력: 최단 거리 테이블(`dist`)
dist = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
dist[i][j] = Integer.parseInt(st.nextToken());
}
}
`need[i][j] = true`: i -> j 간선 실제 존재한다고 가정
=> 실제로 불필요한 간선 나중에 제거
needed = new boolean[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
Arrays.fill(needed[i], true);
}
Floyd-Warshall
- `dist[i][j] > dist[i][k] + dist[k][j]`: 중간 노드 거쳐서 더 짧으면 => 모순 -> -1
- `dist[i][j] == dist[i][k] + dist[k][j]`: 중간 노드 k로 같은 비용 => 직접 간선 불필요
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i == j || i == k || j == k) continue;
if (dist[i][j] > dist[i][k] + dist[k][j]) {
System.out.println(-1);
return;
}
if (dist[i][j] == dist[i][k] + dist[k][j]) {
needed[i][j] = false;
}
}
}
}
코드
import java.io.*;
import java.util.*;
// 궁금한 민호
public class boj_1507 {
static int N;
static int[][] dist;
static boolean[][] needed;
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 + 1][N + 1];
for (int i = 1; i <= N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
dist[i][j] = Integer.parseInt(st.nextToken());
}
}
needed = new boolean[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
Arrays.fill(needed[i], true);
}
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i == j || i == k || j == k) continue;
if (dist[i][j] > dist[i][k] + dist[k][j]) {
System.out.println(-1);
return;
}
if (dist[i][j] == dist[i][k] + dist[k][j]) {
needed[i][j] = false;
}
}
}
}
int ans = 0;
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) {
if (needed[i][j]) ans += dist[i][j];
}
}
System.out.println(ans);
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/Graph] 백준 5214 - 환승 (Java) (0) | 2025.12.04 |
|---|---|
| [BOJ/PriorityQueue] 백준 1781 - 컵라면 (Java) (0) | 2025.12.01 |
| [BOJ/Floyd-Warshall] 백준 13168 - 내일로 여행 (Java) (0) | 2025.11.27 |
| [BOJ/Floyd-Warshall + DFS] 백준 17182 - 우주 탐사선 (Java) (0) | 2025.11.27 |
| [BOJ/MST] 백준 2887 - 행성 터널 (Java) (0) | 2025.11.27 |