[백준] 11404 플로이드

 

문제 출저

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

11404번: 플로이드

 

 

문제 풀이

도시의 갯수 n이 주어지고 도시에서 도시로 이동하는 경로와 비용을 제공하는 정보가 m개 주어진다. 

이 때, 모든 도시에서 다른 도시로 가는 비용의 최솟값을 구하는게 이 문제의 목적이다. 

 

시작 도시를 넣으면 시작 도시에서 다른 도시로 가는 최소 비용을 구하는 함수인 search를 만들었다.

search는 BFS를 이용하여 탐색을 진행했고 answer 배열에 최소 비용을 기입했다.

탐색을 할 때 answer의 비용이 새로 탐색해서 나온 비용보다 크다면 최고값이 answer 기록되게끔 업데이트 치면서 진행했다. 

 

 

소스 코드 

package baekjoon.backjoon9;

/*
23.09.01
플로이드
https://www.acmicpc.net/problem/11404


 */


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class B11404 {

    static int n;
    static int m;
    static int[][] board;
    static int[][] answer;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        board = new int[n][n];

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

            if(board[a][b] == 0) {
                board[a][b] = c;
            }
            else if(board[a][b] > c) {
                board[a][b] = c;
            }
        }

        answer = new int[n][n];


        for(int i = 0; i < n; i++) {
            search(i);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                sb.append(answer[i][j] + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    public static void search(int start) {

        Queue<dot> que = new LinkedList<>();
        que.add(new dot(start, 0));

        while (!que.isEmpty()) {
            dot d = que.poll();

            for(int i = 0; i < n; i++) {

                if(i == start) {
                    continue;
                }

                int cost = board[d.start][i];
                if(cost != 0) {
                    if(answer[start][i] == 0) {
                        answer[start][i] = d.cost + cost;
                        que.add(new dot(i, d.cost + cost));
                    }
                    else if(answer[start][i] > d.cost + cost) {
                        answer[start][i] = d.cost + cost;
                        que.add(new dot(i, d.cost + cost));
                    }
                }

            }

        }

    }

    public static class dot {
        int start;
        int cost;

        dot(int start, int cost) {
            this.start = start;
            this.cost = cost;
        }
    }
}