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

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

SW Expert Academy

---

문제 해석

이 문제는 사회과학 연구에서 사용되는 네트워크 중요도 척도인 'Closeness Centrality' (CC)을 계산하는 문제이다. 네트워크 상의 모든 사용자 간 최단 경로의 합으로 정의된다. 각 사용자에 대해 다른 모든 사용자까지의 최단 경로를 더한 후, 가장 작은 값을 가진 사용자의 CC 값을 찾는 것이 목표다.

풀이 과정

이 문제의 풀이는 플로이드-와샬 알고리즘을 사용하여 모든 노드 쌍에 대한 최단 거리를 계산하는 것을 기본으로 한다. 주어진 인접 행렬에서 직접 연결되지 않은 노드 간의 거리는 매우 큰 값(1000)으로 초기 설정한다. 이후, 모든 노드 쌍에 대해 중간 노드를 거쳐 경로를 단축할 수 있는지 확인하며 행렬을 갱신한다. 모든 노드에 대해 계산된 최단 거리의 합을 구하고, 이 중 최소값을 결과로 반환한다.

코드

package edu.ssafy.im.SWEA.D6;

import java.io.*;
import java.util.StringTokenizer;

public class Solution {
    private static int N;
    private static int[][] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int TC = Integer.parseInt(br.readLine());
        for (int T = 1; T <= TC; T++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            graph = new int[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    graph[i][j] = Integer.parseInt(st.nextToken());
                    if (graph[i][j] == 0 && i != j) graph[i][j] = 1000;  // 직접 연결되지 않은 노드 간 거리 설정
                }
            }
            sb.append("#").append(T).append(" ").append(sol()).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static int sol() {
        // 플로이드-와샬 알고리즘을 사용한 모든 쌍 최단 경로 계산
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (i == j) continue; // 자기 자신으로의 경로는 제외
                    graph[i][j] = Math.min(graph[i][k] + graph[k][j], graph[i][j]);
                }
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            int sum = 0;
            for (int j = 0; j < N; j++) {
                sum += graph[i][j];  // 모든 노드까지의 거리 합 계산
            }
            ans = Math.min(ans, sum);  // 최소 CC 값 찾기
        }

        return ans;
    }
}

시간 복잡도 분석

플로이드-와샬 알고리즘의 시간 복잡도는 𝑂(𝑁3)O(N3)이다. 여기서 𝑁N은 최대 1000까지 가능하므로, 최악의 경우 알고리즘은 약 1,000,000,000번의 연산을 수행할 수 있다. 실제 시나리오에서는 입력 데이터의 크기와 테스트 케이스의 수에 따라 성능이 결정된다.

느낀점

네트워크 분석에 사용되는 중심성 지표를 계산하는 이 문제는 그래프 이론의 기본적인 알고리즘을 활용하는 좋은 실습이었다. 최단 경로 알고리즘의 여러 변형 중 하나인 플로이드-와샬 알고리즘의 이해도를 높일 수 있는 기회였다.