1263. [S/W 문제해결 응용] 8일차 - 사람 네트워크2

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18P2B6Iu8CFAZN 

SW Expert Academy

 

문제 해석

네트워크 상에서 한 사용자가 다른 모든 사람에게 얼마나 가까운가를 구합니다.

이를 CC라고 칭하고 해당 값을 가장 작게 가지는 사람을 출력합니다.

CC(i) = ∑ j dist(i,j)dist(i, j) 단, dist(i, j)는 노드 i로부터 노드 j까지의 최단 거리이다.

 

문제 해석

모든 순서쌍에 대하여 최단경로를 구해야 합니다.

다익스트라 or 플로이드 와샬 알고리즘을 사용하면 됩니다.

사람의 수도 1000이기 때문에 1000 x 1000을 인접행렬로 잡아도 메모리에 무리가 없을 것으로 판단했습니다.

 

 

해당 풀이는 플로이드 와샬 알고리즘을 활용해 보았습니다.

코드

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

public class Solution_사람네트워크2 {

    static final int INF = 100_000_000;

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

        StringBuilder sb = new StringBuilder();
        int result = 0;
        int[][] dp = null;
        int[][] edges = null;
        StringTokenizer st = null;
        for(int tc=1 ;tc<=T; tc++){
            st = new StringTokenizer(br.readLine()," ");
            int n = Integer.parseInt(st.nextToken());
            dp = new int[n+1][n+1];

            for(int i=1; i<n+1; i++){
                for(int j=1; j<n+1; j++){
                    int tempValue = Integer.parseInt(st.nextToken());

                    if(tempValue == 0 || i==j ){
                        dp[i][j]= INF;
                        continue;
                    }
                    dp[i][j] = tempValue;
                }
            }
            //입력 끝

            //1~n번 반복  i = 거쳐가는 노드
            for(int i=1; i<n+1; i++){
                //dp배열 갱신
                for(int j=1; j<n+1; j++){
                    if(i==j) continue;
                    for(int k=1; k<n+1; k++){
                        if(j==k || i == k ) continue;
                        dp[j][k] = Math.min(dp[j][k] , dp[j][i] + dp[i][k]);
                    }
                }
            }

            result = Integer.MAX_VALUE;
            for(int i=1; i<n+1; i++){
                int sum = 0;
                for(int j=1; j<n+1; j++){
                    if(dp[i][j] == INF) continue;
                    sum+= dp[i][j];
                }
                result = Math.min(result,sum);
            }

            sb.append("#"+ tc + " " + result + "\n");
        }
        System.out.println(sb.toString());
    }
}