[백준] 2660. 회장뽑기 (Java)

 

문제

2660번: 회장뽑기

 

알고리즘

플로이드 워셜

 

 

풀이

모든 회원과 친구이면 1점,
모든 회원이 친구이거나 친구의 친구이면 2점,
모든 회원이 친구이거나 친구의 친구이거나 친구의 친구의 친구이면 3점
...

위에 적힌 문제의 조건을 생각해보면

 

어떤 회원의 점수는 모든 간선의 가중치가 1인 그래프에서 다른 모든 회원까지 가는 최단거리 중 최댓값임을 알 수 있다.

 

따라서 플로이드 워셜 알고리즘을 통해 모든 회원에서 다른 모든 회원까지 거리를 계산한 후,

다른 모든 회원까지 가는 최단거리의 최댓값이 가장 작은 회원의 번호를 오름차순으로 출력한다.

 

 

코드

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int N = Integer.parseInt(br.readLine());

		int[][] graph = new int[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (i != j) graph[i][j] = 87_654_321;
			}
		}

		while (true) {
			st = new StringTokenizer(br.readLine(), " ");
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());

			if (A == -1)
				break;

			graph[A][B] = 1;
			graph[B][A] = 1;
		}

		for (int k = 1; k <= N; k++)
			for (int i = 1; i <= N; i++)
				for (int j = 1; j <= N; j++)
					graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);

		int[] scoreList = new int[N + 1];
		int minScore = 87_654_321;
		for (int i = 1; i <= N; i++) {
			int score = 0;
			for (int j = 1; j <= N; j++) {
				score = Math.max(score, graph[i][j]);
			}
			scoreList[i] = score;
			minScore = Math.min(minScore, score);
		}

		ArrayList<Integer> candiList = new ArrayList<>();
		for (int i = 1; i <= N; i++) {
			if (scoreList[i] == minScore)
				candiList.add(i);
		}

		System.out.println(minScore + " " + candiList.size());
		for (int num : candiList)
			System.out.print(num + " ");
	}
}