BOJ G4 1956 운동 JAVA

1956번: 운동

---

문제 읽기

처음에 문제를 읽고 풀었을 때는 dfs로 풀었었다. 그런데 3퍼센트 쯤에 시간 초과가 나와서 그냥 다른 방법을 생각해야겠구나 싶었다.

최단 거리니까 다음과 같은 세 가지 방법이 있었다.

1. 다익스트라
2. 벨만포드
3. 플로이드워샬

각각은 사용하는 경우가 다양한데, 처음엔 다익스트라? 생각했다가 시작 지점이 정해져 있지 않기 때문에 다익스트라를 하려면 여러 번 돌려야만 했다. 그래서 모든 지점에서 다른 모든 지점까지의 최단 거리를 구할 수 있는 플로이드 워샬로 선택했다.

---

문제 풀기

알고리즘을 생각하니 풀이는 어렵지 않았다.

 

플로이드 워샬을 한 번 돌리면 모든 지점에서 다른 모든 지점까지의 최단 거리를 구할 수 있기 때문에, 돌리고, 현 지점에서 다른 지점을 거쳐 다시 현 지점까지 오는 최단 거리를 갱신하는 식으로 구했다.

코드를 보면 쉽게 이해가 될 것 같다.

 

참고로 플로이드 워샬 알고리즘에 대한 설명은 다음 링크에서 확인할 수 있다.

Floyd-Warshall, 플로이드 워샬 알고리즘

---

코드

package ps.ㄱSolving;

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

public class BOJ_G4_1956_운동 {
    static int V, E;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(in.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        int INF = Integer.MAX_VALUE / 2;
        int[][] dist = new int[V+1][V+1];
        for (int i = 0; i < V+1; i++){
            Arrays.fill(dist[i], INF);
        }
        for (int i = 0; i < E; i++){
            st = new StringTokenizer(in.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            dist[a][b] = cost;
        }

        //플로이드 워샬 - 모든 노드에서 모든 노드로 가는 최솟값

        for (int k = 1; k <= V; k++){
            for (int i = 0; i <= V; i++){
                for (int j = 0; j <= V; j++){
                    dist[i][j] = Math.min(dist[i][k] + dist[k][j], dist[i][j]);
                }
            }
        }

//        for (int i = 1; i < V+1; i++){
//            System.out.println(Arrays.toString(dist[i]));
//        }

        int minCost = INF;
        for (int start = 1; start <= V; start++){
            for (int mid = 1; mid <= V; mid++){
                if (start == mid) continue;

                minCost = Math.min(minCost, dist[start][mid] + dist[mid][start]);
            }
        }
        System.out.println((minCost == INF)? -1 : minCost);
    }
}