[SW expert Academy] SWEA 1263번 사람 네트워크2 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [SW expert Academy] SWEA 1263번 사람 네트워크2 자바(Java)

1) 난이도 : D6

 

2) 문제번호 : 1263번

 

3) 문제 출처

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

SW Expert Academy

 

2. 문제

어떤 사화과학 연구 단체에서 사람의 네트워크에 대하여 여러 가지 측정 방법을 사용하여 연구하기로 하였다.

이를 위해 우선 주어진 사람 네트워크에서 누가 가장 영향력이 있는 사람인지를 알 수 있는 척도로서 다음을 분석하는 프로그램을 작성하시오.

단, N은 입력 사람 네트워크 (그래프)의 노드 수이다.

Closeness Centrality(CC):Closeness는 네트워크 상에서 한 사용자가 다른 모든 사람에게 얼마나 가까운가를 나타낸다.

따라서 사용자 i의 CC(i)는 다음과 같이 계산된다.

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

예제 1)

위의 예제는 사람 네트워크에서 사용자 2의 dist합이 가장 작으며, CC(2) = 4임을 통해 사용자 2가 모든 다른 사용자들로부터 가장 가까운 사용자이다.

예제 2)
 

위의 예제는 사람 네트워크에서 사용자 3의 dist합이 가장 작으며, CC(3) = 5임을 통해 사용자 3이 모든 다른 사용자들로부터 가장 가까운 사용자이다.
 

 

3. 제약사항

입력으로 주어지는 사람 네트워크에서 노드 자신을 연결하는 간선은 없다.

또한 사람 네트워크는 하나의 연결 요소(connected component)로 구성되어 있다.

단, 사람 네트워크의 최대 사용자 수는 1,000 이하이다.

테스트 케이스들은 아래의 그룹들로 이루어져 있다.
그룹 1 싸이클이 없고 N <= 10 인 경우
그룹 2 싸이클이 없고 10 < N <= 100 인경우
그룹 3 싸이클이 있고 N<= 10
그룹 4 싸이클이 있고10 < N <= 100
그룹 5 모든 경우가 존재하고 100 < N <= 1000

 

4. 입력

맨 위의 줄에는 전체 테스트 케이스의 수 T가 주어진다.

그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 한 줄에 주어지며, 사람 수인 양의 정수 N이 주어진 다음, 사람 네트워크의 인접 행렬이 행 우선 (row-by-row) 순으로 주어진다.

단, 각 숫자 사이에는 1개의 공백이 주어진다.

 

5. 출력

총 T줄에 T개의 테스트 케이스 각각에 대한 답을 한 줄에 출력한다.

각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음, 각 테스트 케이스에 주어진 사람 그래프에서 사람들의 CC 값들 중에서 최솟값을 한 줄에 출력한다.

 

6. 풀이

- 이 문제는 플로이드 워셜 알고리즘으로 풀었다.

- 플로이드 워셜 알고리즘은 출발지 -> 경유지-> 도착지 순으로 풀거나 경유지 -> 출발지 -> 도착지 순으로 풀면 된다.

- 인접행렬을 구하여 경유지를 거칠 경우에 인접행렬을 계속 갱신을 해준다.

- 단 번에 가는것이 경유지(K)를 거치는 것보다 크다면 인접행렬 i,j 위치에 경유치를 거친 값을 넣는다.

- 그래서, 이 과정이 끝난 인접행렬에서 각 행마다의 값을 찾아서 최소값의 CC를 찾으면 된다.

7. 소스 코드

import java.util.*;
import java.io.*;
 
public class Solution {
    static final int INF = 9999999;
    static int[][] adjMatrix;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); //테스트케이스 개수
         
        for(int tc=1;tc<=T;tc++) {
            int N = sc.nextInt(); // 사람 수
             
            //인접행렬
            adjMatrix = new int[N][N];
             
            //인접행렬 입력
            for(int i=0;i<N;i++) {
                for(int j=0;j<N;j++) {
                    adjMatrix[i][j] = sc.nextInt();
                     
                    //자기자신으로의 인접 정보가 아니고 인접해있지 않다면 INF로 채우기
                    if(i!=j && adjMatrix[i][j]==0) adjMatrix[i][j] = INF;
                }
            }
             
            for(int k=0;k<N;++k) {
                for(int i=0;i<N;++i) {
                    if(i==k) continue;
                    for(int j=0;j<N;++j) {
                        if(i==j || k==j) continue;
                        if(adjMatrix[i][j]>adjMatrix[i][k]+adjMatrix[k][j]) {
                            adjMatrix[i][j] = adjMatrix[i][k]+adjMatrix[k][j];
                        }
                    }
                }
            }
             
            int min = Integer.MAX_VALUE;
             
            for(int i=0;i<N;i++) {
                int sum = 0;
                for(int j=0;j<N;j++) {
                    sum += adjMatrix[i][j];
                }
                min = Math.min(min, sum);
            }
             
            System.out.printf("#%d %d\n",tc,min);
        }
    }
}

---