[백준1956ㅣ운동][JAVA]

문제

마을-마을 사이의 거리가 주어질 때
마을-마을이 연결되어 있으면서 최소인 거리를 구하라.
단, 구할 수 없을 시 -1 출력

🕦 풀이시간 : 30분

---

💡 아이디어

아이디어에 도달할 때까지..

처음에 이 문제를 보았을 때 솔직히 감이 거의 안 잡혔다.
그나마 생각했던 것이 사이클이 존재하는지 체크해서 사이클이 있는 후보군을 먼저 골라낸 다음 뭐를 해볼까? 라는 생각을 했었는데 뭔가 이게 아닐 거 같다는 생각이 계속 들었고 일단 다른 문제로 넘어갔는데 정말 신기하게 오늘 수업을 들으러가서 앉아있는데 이 생각이 번뜩 들었다!

아이디어

일단 이 문제를 해결하기 전날에 플로이드 와셜을 풀었다. 플로이드 와셜은 <단방향> <양수> 거리가 주어졌을 때 모든 점에서의 최소 거리를 구하면 되는 문제이다.

플로이드를 이용해서 각 정점 간의 거리를 구했다면 우리는 여기서 사이클이 존재하는 지 여부를 체크할 수 있다.

사이클이 존재한다는 것은 해당 마을1 -> 마을3 , 마을3 -> 마을1 이라는 것이고 코드 상으로는 0과 MAX값이 아니라는 의미이다!

이것을 조건으로 걸고 조건에 부합한다면 minCycle를 갱신하며 모든 거리를 확인하면 되겠다!

---

💻 코드

import java.io.*;
import java.util.*;

/*
    플로이드 와셜
    [Time] 삼중 for -> O(n*n*n)
    [form] 인접행렬 ar[1][2] -> (1->2)
    [How]
    for 경유할 곳
        for 시작
            for 도착
                거리 최소 갱신
* */

public class Main {
    static int[][] dist;
    static final int MAX = 999999999;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int numCity = Integer.parseInt(st.nextToken()); // 첫 번째 입력을 읽어서 numCity 변수에 저장
        int numBus = Integer.parseInt(st.nextToken());
        dist = new int[numCity+1][numCity+1];

        for(int i = 1 ;i <= numCity; i++){
            for(int j = 1; j <= numCity; j++){
                if(i==j)
                    dist[i][i] = 0;
                else
                    dist[i][j] = MAX;
            }
        }

        for(int i = 0 ; i < numBus; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            if(dist[s][e] > cost)
                dist[s][e] = cost;
        }

        for(int i = 1; i <= numCity; i++){
            for(int j = 1; j <= numCity; j++){
                for(int k = 1; k <= numCity; k++){
                    if(dist[j][k] > dist[j][i] + dist[i][k])
                        dist[j][k] = dist[j][i] + dist[i][k];
                }
            }
        }

        int minCycle = MAX;
        for(int i = 1 ;i <= numCity; i++){
            for(int j = 1; j <= numCity; j++){
                if(dist[i][j] != MAX && dist[j][i] != MAX &&
                        dist[i][j] > 0 && dist[j][i] > 0){
                    minCycle = Math.min(minCycle, dist[i][j] + dist[j][i]);
                }
            }
        }

        if(minCycle != MAX)
            System.out.print(minCycle);
        else
            System.out.print(-1);

//        for(int i = 1 ;i <= numCity; i++){
//            for(int j = 1; j <= numCity; j++){
//                if(dist[i][j] == 99999999)
//                    System.out.print("X" + " ");
//                else
//                    System.out.print(dist[i][j] + " ");
//            }
//            System.out.println();
//        }
    }
}