운동(백준_1956)

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

1956번: 운동

 

문제 설명

1번 부터 V번까지 번호가 매겨져 있는 마을에서 운동을 하기 위해 경로를 찾으려고 한다.

운동을 한 후에 다시 시작점으로 돌아오는 코스를 짤 때, 도로 길이의 합이 최소가 되도록 찾아라!!

구해야하는 것을 정리해 보면

• 싸이클을 찾아라
• 그 때, 도로의  합은 최소여야 한다.

이 정도이다.

 

문제에 대한 아이디어

일단 이 문제를 보고 처음 든 생각은 다익스트라를 사용할까 였다. 하지만 이 문제는 1 : N이 아니다.

하나의 출발점에서 다른 여러 지점으로 가는 최소 비용을 찾는것이 아니라 모든 지점에서 모든 지점으로 갈 때, 최소 비용을 찾는 것이다. 즉 N : N 방법일 때 쓰는 플로이드 워셜 알고리즘을 사용해야 한다!!

 

플로이드 워셜 알고리즘으로 문제해결하기!!

기본적인 플로이드 워셜 알고리즘처럼 이차원 배열을 만든 뒤 3차 for문을 돌면서 

arr[처음][마지막] >= arr[처음][중간] + arr[중간][마지막]을 검사한다. 이렇게 하면 그 지점까지 가는 최소 비용을 찾을 수 있다. 즉, arr[1][2] 는 1에서 2로갈때 최소 비용이다.

 

그럼 싸이클은 어떻게 확인할수 있을까?

arr[1][2]가 제일처음 지정한 숫자가 아니라 최소 비용으로 되어 있을 때, arr[2][1] 도 최소 비용으로 되어 있는지 검사하는 것이다. 왜냐하면 어떤 경로로 가든 arr[1][2]는 1에서 2를 간것이고 arr[2][1]은 2에서 1로 갈 수 있다는 것이다.

즉, 싸이클이 형성된다. 그러므로 우리는 이것만 조사해보면 된다.

 

구현

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

public class 백준_1956 {
    static int arr[][];
    public static void main(String[] args) throws IOException {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(buf.readLine());
        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        arr = new int[v+1][v+1];
        for(int i = 0; i<=v; ++i){
            for(int j = 0; j<=v; ++j){
                if(i == j) arr[i][j] = 0;
                else arr[i][j] = 987654321;
            }
        }
        for(int i =0; i<e; ++i){
            st = new StringTokenizer(buf.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            arr[a][b] = c;
        }
        //플로이드 워셜 알고리즘
        for(int m = 1; m <= v; ++m){
            for(int s = 1; s<=v; ++s){
                for(int en = 1; en <=v; ++ en){
                    if(arr[s][en] >= arr[s][m] + arr[m][en]){
                        arr[s][en] = arr[s][m] + arr[m][en];
                    }
                }
            }
        }
        //이차원 배열을 돌면서 cycle인지 검사한다
        int result = 987654321;
        for(int i = 1; i<=v; ++i){
            for(int j =1; j<=v; ++j){
                if(arr[i][j] != 987654321 && arr[j][i] != 987654321 && i!=j){
                    result = Math.min(result, arr[i][j] + arr[j][i]);
                }
            }
        }
        if(result == 987654321){
            System.out.println(-1);
        }
        else System.out.println(result);
    }
}

 

https://github.com/Heron-Woong/CodingTest_Practice/commit/810544dca4ac47744cb23765aea563d167d61c2a

백준_1956, 운동 · Heron-Woong/CodingTest_Practice@810544d