1956번 - 운동

2024-07-13

#JAVA#백준

문제 링크

문제 풀이 시간 : 10분

문제 요약

•
V 개의 마을과 E 개의 도로로 구성된 도시가 있다.

•
도로를 따라 운동을 하기위한 경로를 찾는다.

•
사이클을 찾되 길이의 합이 최소가 되도록 한다.

•
경로를 찾을 수 없는 경우 -1을 출력한다.

문제 풀이

처음에는 각 마을 별로 모든 경로를 탐색해보면서 사이클이 있는지 없는지 확인하려고 했는데

그렇게 하면 너무 복잡하고 오히려 어려울 것 같아서 다른 방법을 생각했다.

그래서 생각한게 플로이드를 이용하는 것이다.

원래 플로이드에서는 자기 자신을 향하는 경로의 길이를 0으로 설정하지만

이 길이를 0이 아니라 무한대로 설정해둔다면?

모든 경로를 탐색하는 과정에서 사이클이 생기면 자기자신으로 가는 길이가 구해질 것이라고 생각했따.

그렇게 했더니 아주 쉽게 구할 수 있었따.

정답 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    public static long[][] cost;

    public static void main(String[] args) throws IOException{
        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());

        cost = new long[V + 1][V + 1];

        for(int i=1;i<=V;i++){
            for(int j=1;j<=V;j++){
                cost[i][j] = Integer.MAX_VALUE;
            }
        }

        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());

            cost[a][b] = c;
        }

        for(int k=1;k<=V;k++){
            for(int i=1;i<=V;i++){
                for(int j=1;j<=V;j++){
                    cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);
                }
            }
        }
        long ans = Integer.MAX_VALUE;
        for(int i=1;i<=V;i++){
            ans = Math.min(ans, cost[i][i]);
        }
        if(ans==Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(ans);
    }
}