[SWEA] 1263 : 사람 네트워크2 - Java

문제

해당 문제는 모든 정점 -> 모든 정점 최단거리를 구해야 하는 문제.
그렇기에 플로이드 워셜을 떠올렸어야 했다.

내 코드

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int T, INF = 1000000;
    static int[][] g;

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            g = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    g[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(g[i][j] == 0) g[i][j] = INF;
                    if(i==j) g[i][j] = 0; // ! 본인은 0
                }
            }

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

            // ! 모든 노드에 대한 최소 거리 계산
            int minSum = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                int sum = 0;
                for (int j = 0; j < n; j++) {
                    sum += g[i][j];
                }
                minSum = Math.min(minSum, sum);
            }

            System.out.println("#" + t + " " + minSum);
        }


    }

    public static void printBoard(int[][] g){
        for (int i = 0; i < g.length; i++) {
            for (int j = 0; j < g[i].length; j++) {
                System.out.print(g[i][j] + " ");
            }
            System.out.println();
        }
    }

}

코멘트

플로이드 워셜 기본 세팅
원래대로라면, 무한대로 모든 값을 초기화 해준 후 입력을 받고, 특정 좌표에 값을 넣어준다.
그 후 본인의 좌표 (i,i)에는 0으로 넣어준다.

• 기본 세팅 끝

그 후 플로이드 워셜 적용.
모든 정점 -> 모든 정점으로의 거리를 구할 수 있다.

이 문제에서는 특정 좌표에서 시작해서 모든 좌표로 가는 합의 최단거리를 구하는 것이었다.
반복문 돌려서 최솟값 찾으면 끝.