사람 네트워크2

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18P2B6Iu8CFAZN&categoryId=AV18P2B6Iu8CFAZN&categoryType=CODE&problemTitle=1263&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

풀이

그래프가 주어지고 한 노드에서 다른 모든 노드로 가는 경로의 합이 최소인 노드를 찾아 그 때 합의 최소를 출력하면 되는 문제이다.

모든 노드 쌍의 최단 경로를 계산해야하기 때문에 플로이드-워샬 알고리즘을 적용해서 모든 최단 경로를 계산하고 각 노드 별 최단경로들의 합의 최소를 찾으면 된다.

코드

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

public class Solution {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int n, m;
    static int[] p;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            String[] line = br.readLine().split(" ");
            int n = Integer.parseInt(line[0]);
            int[][] graph = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++)
                    graph[i][j] = 10000000;
            }

            for (int i = 1; i < line.length; i++) {
                int x = (i - 1) / n;
                int y = (i - 1) % n;
//                System.out.println(x + ", " + y);
                int num = Integer.parseInt(line[i]);
                if(num != 0)
                    graph[x][y] = num;
            }
            int[][] dist = new int[n][n];

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

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

            int min = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                int a = Arrays.stream(dist[i]).sum();
                min = Math.min(min, a);
            }
            bw.write("#" + (t + 1) + " " + min + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

}