백준 | 1956번. 운동 - 플로이드에 대한 RE 풀이

https://www.acmicpc.net/problem/1956

1956번: 운동

문제

V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자.

당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.

도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오. 두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다.

입력

첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의미이다. (a → b임에 주의) 거리는 10,000 이하의 자연수이다. (a, b) 쌍이 같은 도로가 여러 번 주어지지 않는다.

출력

첫째 줄에 최소 사이클의 도로 길이의 합을 출력한다. 운동 경로를 찾는 것이 불가능한 경우에는 -1을 출력한다.

---

💚 의문점 해결 내용

스터디 때 의문점이 생겼던 부분은 일반적인 플로이드 문제를 풀 때에 i=j 인 인접 행렬 상 대각선 부분을 보통은 0 으로 초기화를 해두는데 어떻게 distance[i][i] 로 접근한 값이 최종적으로 answer에 답을 뱉을 수 있는가 였습니다.

보통의 플로이드 문제는 i=j 인 부분은 0으로 초기화, 그 외의 부분은 INF로 초기화를 해두고,
i != j 인 부분은 distance[i][j] 는 i -> k->  j  (즉, k 경유지를 거친 i에서 j로의 최단 경로를 저장) 하도록 하는데요.
i==j 인 부분은 distance[i][i]는   i-> i (i로 출발해 i로 도착하는 자기 자신에 대한 경로는 0 으로 생각합니다)

그런데, i=j 의 대각선 부분을 0으로 초기화 하지 않고 모두 INF로 초기화를 해둔다면 
i != j 인 부분 distance[i][j] 에 대한 부분은 여전히 (  k 경유지를 거친 i에서 j로의 최단 경로를 저장) 하겠지만,
i==j 인 부분 distance[i][i] 역시도 i-> k -> i (즉, i로 출발해 특정 k경유지를 거쳐서 다시 i로 오는 값을 의미하게 됩니다) 

0으로 초기화 되지 않은 경우에는 distance[][] 에 있는 모든 값들이 플로이드를 통한 갱신 대상이 되므로
i = j 인 인접 행렬 상 대각선 부분도 
플로이드로 3중 for문을 순회하면서
distnace[i][i] = Math.min(distance[i][i], ditstance[i][k] + distance[k][i] ) 로 갱신 처리 되기 때문입니다.

풀이 설명

💚 제출 코드

import java.util.Arrays;
import java.util.Scanner;

/**
 * 1956번. 운동 - 플로이드 문풀 
 * @author MYLG
 *
 */
public class Main {
	static final int INF = 10000001;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int V = kb.nextInt();
		int E = kb.nextInt();
		
		int[][] distance = new int[V+1][V+1];
		
		for(int i=1; i<=V; i++) {
			Arrays.fill(distance[i], INF); //그냥 모든 distance에 대한 INF 초기화 처리함
		}
		
		//세팅
		for(int i=0; i<E; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int val = kb.nextInt();
			if(distance[a][b] > val) {
				distance[a][b] = val;
			}
		}
		
		//플로이드 시작
		for(int k = 1; k<=V; k++) {
			for(int i=1; i<=V; i++) {
				for(int j=1; j<=V; j++) {
					if(distance[i][j] > distance[i][k] + distance[k][j]) {
						distance[i][j] = distance[i][k] + distance[k][j];
					}
				}
			}
		}
		
		/**
		 * 
		 * disatnce[i][i] : i -> i : i로 출발해서 i로 도착 (즉, 자기 자신에 대한 경로이므로 0 처리를 해둠)
		 * 그러나, i=j 부분을 따로 0처리를 하는 대신 INF로 초기화를 해두었기 때문에, 
		 * 플로이드 적용 후 distance[i][i] 에 대한 최단거리가 다음과 같이 갱신될 것이다. 
		 * distance[i][i] = i -> k -> i : 즉, 특정 경유지 k를 거쳐서 들어온 최단 거리를 저장하도록 함 (결과적으로는 사이클이 담김)
		 *  
		 */
		int answer = INF;
		for(int i=1; i<=V; i++) { 
			//answer = Math.min(answer, distance[i][j] + distance[j][i] ) 가 아니라 
			answer = Math.min(answer, distance[i][i]); //이렇게 i,i (즉, i -> 특정 경유지 k -> i 자기 자신으로 되돌아온 (사이클) 최단 경로가 담기게 되는 것이다. )
		}
		System.out.println(answer);
	}

}

---

💚 P.S

 만약 이 문제가 구하라는 사이클 상의 최단 경로를 구하기 위해 distance[i][i] (i->i) 정의를 의도적으로 '왕복 가능한 정점 간의 최단 경로'로 두고 풀이에 접근한 거였다면 우수한 접근이라고 생각합니다.
 그러나, 그럴 의도가 없이 풀었던 것이라면, 일반적으로 플로이드를 풀 때 distance[i][i]의 값을 이런 방식으로 사용하는 경우가 많지 않기 때문에 풀이 시 잘 설계하는 것이 중요할 것 같습니다 !