문제
N명의 회원 간 친구 관계가 주어질 때, 각 회원의 "점수"(가장 먼 회원까지의 거리)를 구하고 점수가 가장 낮은 회원을 회장 후보로 선출하라.
입력
첫째 줄에 N, 이후 친구 관계가 주어지며 -1 -1로 종료한다.
출력
회장 후보의 점수, 인원 수, 후보 번호를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 1 2 2 3 3 4 4 5 2 4 5 3 -1 -1 | 2 3 2 3 4 |
풀이
플로이드-워셜로 모든 쌍의 최단 거리를 구한 뒤, 각 회원의 최대 거리(점수)가 최소인 사람을 찾는다.
- 인접 행렬에 친구 관계를 거리 1로 기록한다
- 플로이드-워셜로 모든 쌍의 최단 거리를 구한다
- 각 회원의 점수 = 다른 모든 회원까지의 최단 거리 중 최댓값
- 점수가 가장 낮은 회원을 회장 후보로 선출한다
핵심 아이디어: 플로이드-워셜로 O(V³)에 모든 쌍 최단 거리를 구하면 각 회원의 점수를 바로 계산할 수 있다.
코드
package day649;
import java.io.*;
import java.util.*;
public class Day649BOJ2660회장뽑기 {
static final int INF = 987654321;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[][] arr = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i != j) {
arr[i][j] = INF;
}
}
}
while (true) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
if (x == -1 && y == -1) {
break;
}
arr[x][y] = arr[y][x] = 1;
}
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (arr[i][j] > arr[i][k] + arr[k][j]) {
arr[i][j] = arr[i][k] + arr[k][j];
}
}
}
}
int readerScore = INF;
int[] scoreArr = new int[N + 1];
for (int i = 1; i <= N; i++) {
int score = 0;
for (int j = 1; j <= N; j++) {
if (arr[i][j] != INF) {
score = Math.max(score, arr[i][j]);
}
}
scoreArr[i] = score;
readerScore = Math.min(readerScore, score);
}
StringBuilder title = new StringBuilder();
title.append(readerScore + " ");
int readerNum = 0;
StringBuilder body = new StringBuilder();
for (int i = 1; i <= N; i++) {
if (readerScore == scoreArr[i]) {
readerNum++;
body.append(i + " ");
}
}
title.append(readerNum + "\n");
bw.write(title.toString());
bw.write(body.toString() + "\n");
bw.flush();
bw.close();
br.close();
}
}복잡도
- 시간: O(V³)
- 공간: O(V²)