문제
난이도: 골드 4
V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자.
당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.
도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오. 두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다.
입력
V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자.
당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.
도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오. 두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다.
출력
첫째 줄에 최소 사이클의 도로 길이의 합을 출력한다. 운동 경로를 찾는 것이 불가능한 경우에는 -1을 출력한다.
문제 분석
플로이드 워셜 알고리즘을 연습하기 위해 풀어본 문제 3!
기본 플로이드 워셜 알고리즘을 사용하면 되고, '다시 돌아오는 사이클'만 생각해주면 되는 문제
다시 돌아오는 사이클은 생각해보면 1에서 3갔으면 3에서 다시 1로 오는 최단 경로를 더해주면 된다
근데 계속 틀렸다.. 63퍼 정도에서
원인은 최댓값 INF 설정 범위 ㅠ
플로이드 워셜 문제는 INF로 초기화 하는 부분이 존재하는데,
해당 INF 값을 설정하는 게 중요하다
너무 작으면 초기화의 의미가 없고
그냥 Integer.MAX_VALUE를 하면 int 값의 범위를 넘어서 그건 또 안됨
앞으로 987654321로 통일해봐야지..
풀이 방법
기본 플로이드 워셜 알고리즘을 돌려서 dist 배열 완성
플로이드 워셜을 돌렸다면 dist 배열은
1에서 1, 2, 3등을 가는 최소 거리가 저장되어 있다
(당연히 1에서 1은 0으로 초기화 필수)
2중 for문을 통해 dist[i][j] + dist[j][i]이 가장 작은 값을 찾으면 됨! 그게 정답!
운동 경로를 찾는 것이 불가 한 경우는
dist[i][j]이 최댓값이거나, dist[j][i]이 최댓값인 경우는 계산에서 제외시키고
초기화 값이 변하지 않았다면 운동 경로가 없는 것이므로 -1 출력
내 코드
package day_240104;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BJ_Main_1956_운동 {
static final int INF = 987654321;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
int[][] dist = new int[V][V];
for(int i = 0; i<V; i++) {
for(int j = 0; j<V; j++) {
if(i==j) dist[i][j] = 0;
else dist[i][j] = INF;
}
}
for(int i = 0; i<E; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
dist[a-1][b-1] = c;
}
for(int k = 0; k<V; k++) {
for(int i = 0; i<V; i++) {
if(i==k) continue;
for(int j = 0; j<V; j++) {
if(i==j || k==j) continue;
dist[i][j] = Math.min(dist[i][j], dist[i][k]+dist[k][j]);
}
}
}
// for(int i = 0; i<V; i++) {
// System.out.println(Arrays.toString(dist[i]));
// }
int answer = INF;
for(int i = 0; i<V; i++) {
for(int j = 0; j<V; j++) {
if(i == j) continue;
else {
if(dist[i][j] != INF && dist[j][i] != INF) {
int tmp = dist[i][j] + dist[j][i];
answer = Math.min(answer, tmp);
}
}
}
}
System.out.println(answer == INF ? -1 : answer);
}
}
