문제
V개의 마을과 E개의 단방향 도로가 주어졌을 때, 어떤 마을에서 출발하여 다시 그 마을로 돌아오는 사이클 중 최소 비용을 구하는 문제이다. 사이클이 존재하지 않으면 -1을 출력한다.
입력
- 첫 번째 줄: 마을 수 V (1 이상 400 이하), 도로 수 E (1 이상 10,000 이하)
- 이후 E줄: 시작 마을, 도착 마을, 거리
출력
가능한 사이클 중 최소 비용을 출력한다. 사이클이 없으면 -1을 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 4 1 2 1 3 2 1 1 3 5 2 3 2 | 3 |
풀이
플로이드-워셜로 모든 쌍 최단 경로를 구한 후, dist[i][i](자기 자신으로 돌아오는 사이클 길이)의 최솟값을 찾는다.
dist[i][j]를 INF로 초기화한다. (자기 자신 포함,dist[i][i] = INF로 초기화해 사이클 검출에 활용)- 간선 입력 시 동일 구간 중복 도로는
Math.min으로 최솟값을 유지한다. - 플로이드-워셜 3중 for문으로 모든 쌍 최단 경로를 갱신한다.
dist[i][i]를 순회하여 최솟값min을 구하고,min >= INF이면 -1을 출력한다.
핵심 아이디어: dist[i][i]는 노드 i를 출발하여 i로 돌아오는 최단 경로를 나타낸다. 초기화 시 dist[i][i] = INF로 두어야 자기 자신으로의 사이클만 검출할 수 있다. INF로 1e9를 사용하지 않으면 두 INF 값의 합산 시 int 오버플로우가 발생한다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day52BOJ1956운동 {
// 테케 88%실패여서, 구선생님 도움받음.
// 플로이드 값 구할때 2개 값 더하는게 있는데, 최대값으로 하면 초과되버림.
// 최소값 활용하는 식이라 답도 아닌 것 때문에 실패 뜸. 1e9로 충분히 큰값 사용.
static final int INF = (int) 1e9;
static int V, E, min = Integer.MAX_VALUE;
static int[][] dist;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
dist = new int[V + 1][V + 1];
for (int i = 0; i < V + 1; i++) {
for (int j = 0; j < V + 1; j++) {
dist[i][j] = INF;
}
}
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int idx = Integer.parseInt(st.nextToken());
int tIdx = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
dist[idx][tIdx] = Math.min(dist[idx][tIdx], d);
}
System.out.println(floyd());
br.close();
}
private static int floyd() {
for (int k = 1; k < V + 1; k++) {
for (int i = 1; i < V + 1; i++) {
for (int j = 1; j < V + 1; j++) {
dist[i][j] = Math.min(dist[i][k] + dist[k][j], dist[i][j]);
}
}
}
for (int i = 1; i < V + 1; i++) {
min = Math.min(dist[i][i], min);
}
return min >= INF ? -1 : min;
}
}복잡도
- 시간: O(V³) — 플로이드-워셜 3중 for문
- 공간: O(V²) — V x V 거리 행렬