https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18P2B6Iu8CFAZN
어떤 사화과학 연구 단체에서 사람의 네트워크에 대하여 여러 가지 측정 방법을 사용하여 연구하기로 하였다.
이를 위해 우선 주어진 사람 네트워크에서 누가 가장 영향력이 있는 사람인지를 알 수 있는 척도로서 다음을 분석하는 프로그램을 작성하시오.
단, 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이 모든 다른 사용자들로부터 가장 가까운 사용자이다.
[제약 사항]
입력으로 주어지는 사람 네트워크에서 노드 자신을 연결하는 간선은 없다.
또한 사람 네트워크는 하나의 연결 요소(connected component)로 구성되어 있다.
단, 사람 네트워크의 최대 사용자 수는 1,000 이하이다.
테스트 케이스들은 아래의 그룹들로 이루어져 있다.
그룹 1 싸이클이 없고 N <= 10 인 경우
그룹 2 싸이클이 없고 10 < N <= 100 인경우
그룹 3 싸이클이 있고 N<= 10
그룹 4 싸이클이 있고10 < N <= 100
그룹 5 모든 경우가 존재하고 100 < N <= 1000
[입력]
맨 위의 줄에는 전체 테스트 케이스의 수 T가 주어진다.
그 다음 줄부터 T개의 테스트 케이스가 주어진다.
각 테스트 케이스는 한 줄에 주어지며, 사람 수인 양의 정수 N이 주어진 다음, 사람 네트워크의 인접 행렬이 행 우선 (row-by-row) 순으로 주어진다.
단, 각 숫자 사이에는 1개의 공백이 주어진다.
[출력]
총 T줄에 T개의 테스트 케이스 각각에 대한 답을 한 줄에 출력한다.
각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음, 각 테스트 케이스에 주어진 사람 그래프에서 사람들의 CC 값들 중에서 최솟값을 한 줄에 출력한다.
풀이
플로이드 워셜 응용문제이다.
가중치가 없는 그래프이나 BFS보다 플로이드 워셜 실행속도가 더 빠르고, 이전 문제와 같이 경유의 개념이 있는 문제이기에 플로이드 워셜로 풀었다.
package D6;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class S1263_사람네트워크2 {
static int INF = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
int dist[][];
int ans;
for (int t = 1; t <= T; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
dist = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dist[i][j] = Integer.parseInt(st.nextToken());
if (dist[i][j] == 0)
dist[i][j] = INF;
}
} // end input //
// Floyd-Warshall
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 || j == k)
continue;
if (dist[i][k] != INF && dist[k][j] != INF && dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
// dist의 한 행의 합은 그 행의 CC
ans = 0;
int res = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
int sum = 0;
for (int j = 0; j < N; j++) {
if (i == j)
continue; // 자기 자신을 연결하지 않음
sum += dist[i][j];
}
if (sum < res) {
ans = i;
res = sum;
}
}
sb.append("#").append(t).append(" ").append(res).append('\n');
} // end testcase
System.out.println(sb);
}
}결과
후기
처음에 인접리스트에 입력하는 부분에서, 0인 부분을 INF로 정의하지 않고 그대로 두었다.
그랬더니 플로이드 워셜의 dist[i][j] > dist[i][k] + dist[k][j]이 부분에서 논리적 오류가 발생할 수밖에 없었다.
당연히도 dist[i][j]가 계속 0일테니, 최단거리가 갱신이 되지 않았던 것이다.
이전 문제는 INF를 쓰지 않고도 풀 수 있어 이 문제에서도 가능할 줄 알았다.
어쨌든 최단경로를 구하는 것이 목적이기에 INF를 써주어야 한다.
