[BOJ - Gold IV] 운동 / ⭕

운동

1. 제출 코드 (24분 00초 / 플로이드 워셜)

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

public class Main {
    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());

        int[][] dist = new int[V + 1][V + 1];
        int INF = 100000000;
        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());
            dist[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
        }

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

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

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

2. 구현 로직

모든 노드간의 최단 경로를 탐색해야 하고 간선에 가중치가 있는 그래프에서 최소 경로를 찾기 위해 플로이드 워셜을 이용했다.

1. 가중치 테이블 INF로 초기화
2. 마을 이동간의 가중치를 입력받아 초기화
3. i에서 j 마을로 갈 때 k를 거쳐서 가는 최소 가중치 구함
4. 출발한 마을로 다시 돌아와야 하므로 dist[i][i]의 최솟값을 구하여 출력

3. 유의할 점

• 가중치 테이블을 초기화할 때, INF를 MAX_VALUE로 두면 오버플로우가 나는 문제점을 조심해야 한다.