[백준] 1956 - 운동 | Java

📌 문제 정보

[1956번: 운동]

💡 접근 방식

플로이드 와샬 알고리즘을 사용하면 된다.
overflow 방지를 위해 비용이 INF인지 체크도 해주자.
그리고, 사이클을 구해야 하니 답을 구할 땐 (i, j) + (j, i)를 해야한다.
첨에 (i,i)로만 생각했다가 틀렸다 ㅋㅋ

✅ 코드

import java.util.*;

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

public class Main {

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

        final int INF = Integer.MAX_VALUE;

        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());

        int[][] dist = new int[v][v];

        for (int i = 0; i < v; i++) {
            for (int j = 0; j < v; j++) {
                if (i == j) dist[i][j] = 0;
                else dist[i][j] = INF;
            }
        }

        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) -1;
            int b = Integer.parseInt(st.nextToken()) -1;
            int c = Integer.parseInt(st.nextToken());

            dist[a][b] = c;

        }
        for (int k = 0; k < v; k++) {
            for (int i = 0; i < v; i++) {
                for (int j = 0; j < v; j++) {
                    if (dist[i][k] != INF && dist[k][j] != INF) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }

        int answer = INF;
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < v; j++) {
                if (i != j && dist[i][j] != INF && dist[j][i] != INF) {
                    answer = Math.min(answer, dist[i][j] + dist[j][i]);
                }
            }
        }

        System.out.println(answer == INF ? -1 : answer);

    }

}

🔍 주요 코드 설명:

• 어떤 부분에서 어떤 로직이 작동하는지 간단히 주석 또는 설명 추가

🧠 배운 점 & 회고

플로이드-와샬 알고리즘 문제를 처음 풀어 보았다!
그래서 처음 문제를 봤을 땐, 최단 경로니 당연 bfs겠거니 하고 풀었다.
근데 풀 수록 뭔가.. 이게 아닌데...? 싶은 느낌..
사이클을 감지하는 것도 잘 안됐고, 무엇보다 가중치가 있다는 점을 간과했다!
재귀로 풀어보려다 알고리즘 분류를 보니 플로이드-와샬 문제였다.
전에 다익스트라 공부했을 때 어렴풋이 봤던 기억은 있는데, 이렇게 제대로 만난 건 처음이라 후다닥 공부하고 와서 마저 풀었다. 별 거 아니군~!

🧾 결과

플로이드-와샬