[SWEA] 1263. 사람 네트워크2.java

SWEA에서 사람 네트워크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 

SW Expert Academy

 

1263. 사람 네트워크2.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

1263번 사람 네트워크2

문제

어떤 사화과학 연구 단체에서 사람의 네트워크에 대하여 여러 가지 측정 방법을 사용하여 연구하기로 하였다.
이를 위해 우선 주어진 사람 네트워크에서 누가 가장 영향력이 있는 사람인지를 알 수 있는 척도로서 다음을 분석하는 프로그램을 작성하시오.
단, N은 입력 사람 네트워크 (그래프)의 노드 수이다.
Closeness Centrality(CC):Closeness는 네트워크 상에서 한 사용자가 다른 모든 사람에게 얼마나 가까운가를 나타낸다.
따라서 사용자 i의 CC(i)는 다음과 같이 계산된다.
      CC(i) = ∑ j dist(i,j) 단, dist(i,j)는 노드i로부터 노드 j까지의 최단 거리이다.

설명

모든 사람을 하나의 정점으로 놓고 각 정점들에 대해서 모든 가중치가 1인 간선이 연결되어 있다고 생각하면 된다. 각 정점마다 모든 정점에 대한 최단 거리를 구하고 총 합을 계산해야한다. 모든 정점에 대한 최단 경로를 구해야하므로 폴로이드-워셜 알고리즘을 사용한다. 

 

폴로이드-워셜 알고리즘을 통해 계산한 결과에 대해서 어떠한 행 i의 총 합이 CC(i)이다. 모든 CC를 구한 후 그 중 최솟값이 문제의 정답이다.

코드

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

public class 사람_네트워크2_1263 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		int T = Integer.parseInt(br.readLine());
		for(int t=1;t<=T;t++) {
			st = new StringTokenizer(br.readLine()," ");
			int N = Integer.parseInt(st.nextToken());
			
			int[][] dp = new int[N+1][N+1];
			
			for(int i=1;i<=N;i++) {
				for(int j=1;j<=N;j++) {
					if(i==j) {
						st.nextToken();
						dp[i][j] = 0;
					}
					else {
						dp[i][j] = Integer.parseInt(st.nextToken());
						if(dp[i][j]==0)dp[i][j] = N*(N+1)/2;
					}
				}
			}
						
			for(int k=1;k<=N;k++) {
				for(int i=1;i<=N;i++) {
					for(int j=1;j<=N;j++) {
						dp[i][j] = Math.min((dp[i][k]+dp[k][j]),dp[i][j]);
					}
				}
			}
			
			
			int answer = N*(N+1)/2;
			for(int i=1;i<=N;i++) {
				int temp=0;
				for(int j=1;j<=N;j++) {
					temp += dp[i][j];
				}
				if(temp < answer)answer = temp;
			}
			sb.append("#"+t+" "+answer+"\n");
		}
		System.out.println(sb.toString());
	}
}