[백준] 11404번 : 플로이드 Gold4(골드4) - JAVA[자바]

[Gold IV] 플로이드 - 11404

문제 링크

성능 요약

메모리: 42752 KB, 시간: 344 ms

분류

플로이드–워셜, 그래프 이론, 최단 경로

제출 일자

2024년 1월 17일 00:19:23

문제 설명

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

 

접근 방법

1. 입력 받는 값 N은 노드의 개수 버스의 개수 M은 간선의 개수이다. 

2. 각 가중치를 배열에 놓고 모든 노드를 거쳐가면서 최소 값을 넣는 것이다.

3. 노선은 1개가 아닐수도 있기 때문에 최소값으로 시작한다.

4. 비용의 최대값은 100,000이고 도시의 개수 최대값은 100이기 때문에 배열을 최대값인 10,000,000로 놓고 시작한다.

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

public class Main {
    // 도시 노선의 정보를 담는 배열
    static int[][] graph;
    // 도시의 개수
    static int n;
    // 비용의 최대값
    static final int LIMIT = 10000000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        // 도시 개수 입력 받기
        n = Integer.parseInt(br.readLine());
        graph = new int[n][n];
        // 최소값을 찾기 위해 비용의 최대값 100,000 * 최대 도시 100값으로 초기화
        for (int i = 0; i < n; i++) {
            Arrays.fill(graph[i], LIMIT);
        }
        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken()) - 1;
            int to = Integer.parseInt(st.nextToken()) - 1;
            int value = Integer.parseInt(st.nextToken());
            // 노선의 개수는 한개가 아닐수도 있기 때문에 처음 받는 값이 아니라면 최소값 삽입
            if (graph[from][to] > value) {
                graph[from][to] = value;
            }
        }

        // 플로이드 워셜
        floydWarshall();

        // sb에 추가
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j || graph[i][j] == LIMIT) graph[i][j] = 0;
                sb.append(graph[i][j] + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    // 모든 노드를 거쳐가는 플로이드워셜 알고리즘
    private static void floydWarshall() {
        // 거쳐가는 도시
        for (int k = 0; k < n; k++) {
            // 출발 도시
            for (int i = 0; i < n; i++) {
                // 도착 도시
                for (int j = 0; j < n; j++) {
                    // 더 빠른 노선이 있다면 그것으로 초기화 시켜줌
                    if (graph[i][j] > graph[i][k] + graph[k][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                    }
                }
            }
        }
    }
}