[백준] 1956 : 운동 (JAVA), 플로이드-와샬(Floyd-Warshall)

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

1956번: 운동

Solution

사이클을 이루는 도로의 길이의 합이 최소가 되는 것을 찾기 위해서는 모든 정점으로 부터 모든 정점까지의 최단 거리를 구해야한다.

이 때, 가중치 c의 범위가 10,000 이하의 자연수 이므로 음의 가중치를 갖지 않는다. 또한, V가 400이하로 범위가 작다. 다익스트라, 플로이드-와샬 둘 다 가능하다.

나는 플로이드-와샬을 사용했다. 플로이드 와샬 알고리즘의 자세한 내용은 아래 포스트를 참고하자.

2023.01.18 - [알고리즘/개념] - [알고리즘] 플로이드-와샬, Floyd-Warshall

[알고리즘] 플로이드-와샬, Floyd-Warshall

 

주어진 조건을 살펴보면, 정점은 최대 400개이고 하나의 간선의 최대 가중치는 10000이다.
만약 1번 정점에서 400번 정점까지 가기 위해 모든 정점을 다 거쳐야만 한다고 해도 400*10000 보다 적을 것이다.
이를 왕복한다고 해도 400*10000*2 는 int형 범위를 넘지 않는다.

이 문제에서 주의할 점은 1번 정점에서 1번 정점으로 가는 루프(loop) 간선이 존재하는 경우를 고려해줘야한다는 것이다. 이것 때문에 한참 해맸다...

코드

public class P1956 {
    public static final int INF = 4000000;
    static int[][] dist;

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

        dist = new int[V + 1][V + 1];
        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                dist[i][j] = INF;
            }
        }
        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());
            dist[a][b] = c;
        }

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

        int answer = INF*2;
        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                if (dist[i][j] == INF || dist[j][i] == INF) continue;
                if (i == j) {
                    answer = Math.min(answer, dist[i][j]);
                } else {
                    answer = Math.min(answer, dist[i][j] + dist[j][i]);
                }
            }
        }

        if (answer == INF*2) {
            System.out.println(-1);
            return;
        }
        System.out.println(answer);

    }
}