[백준] 1956번. 운동(JAVA)

문제

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

---

풀이(20분)

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

public class Main {

    static int v, e;
    static int[][] graph;
    static final int INF = 1_000_000_000; // 최대 범위

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());

        v = Integer.parseInt(st.nextToken()); // 정점의 개수
        e = Integer.parseInt(st.nextToken()); // 경로의 개수
        graph = new int[v+1][v+1]; // 인덱스를 위해 + 1 하여 초기화

        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph.length; j++) {
                if(i == j) continue; // 시작점과 도착점이 동일한 경우 0
                graph[i][j] = INF; // 최대 범위로 초기화
            }
        }
        for(int i = 0; i < e; i++){ // 경로 입력
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int distance = Integer.parseInt(st.nextToken());
            graph[start][end] = distance; // 시작 -> 도착의 단방향
        }

        floyd(v); // 플로이드-와샬 알고리즘

        int answer = INF;
        for(int i = 1; i <= v; i++){
            for(int j = 1; j <= v; j++){
                if(i == j){
                    continue; // 시작점 == 도착점인 경우 사이클로 안 침
                }
                answer = Math.min(answer, graph[i][j] + graph[j][i]); // 사이클 최소값
            }
        }

        if(answer == INF){ // 바뀐적이 없다면 사이클이 없다는 것
            System.out.println(-1);
            return;
        }

        System.out.println(answer);

    }

    static void floyd(int n) {
        // 경유지
        for (int k = 1; k <= n; k++) {
            // 출발지
            for (int i = 1; i <= n; i++) {
                //도착지
                for (int j = 1; j <= n; j++) {
                    graph[i][j] = Math.min(graph[i][j], graph[i][k]+graph[k][j]);
                }
            }
        }
    }
}

---

문제 풀이 전략

 

사실 플로이드-와샬 알고리즘의 대표적인 문제이다.

이를 모른다면 하단 링크를 참고하여 공부하자.

2025.04.01 - [문제 풀이/도구정리] - [도구정리] 플로이드-와샬(Floyd-Warshall) 알고리즘

[도구정리] 플로이드-와샬(Floyd-Warshall) 알고리즘

 

플로이드-와샬 알고리즘을 참고했다면, 마지막은 다음과 같다.

모든 노드 사이의 거리를 구했으니 왔다 갔다가 되면 사이클이 되는 것이다.

그렇기에 반복을 통해 사이클 중에 최솟값을 구하자!