[백준 2660번] 회장뽑기 (java)

2660번: 회장뽑기

문제를 보자마자 플로이드 워셜 알고리즘이 떠올랐다.

 

어느 회원과 다른 회원과의 점수는 노드 사이의 거리라고 생각할 수 있다.

어느 회원 노드에 대해서 다른 모든 회원 노드와의 거리를 구하고, 그 중에서 가장 큰 거리가 그 회원의 점수가 된다.

모든 회원에 대하여 다른 회원과의 거리를 알아야 하므로 플로이드 워셜 알고리즘을 사용하면 된다.

 

예를 들어, 문제의 예제에서 1번 회원은 2,3,4,5번 회원과의 거리가 각각 1, 2, 2, 3 이다.

이 중에서 가장 큰 값이 1번 회원의 점수가 되므로 1번 회원의 점수는 3이 된다.

 

 

 

소스코드 : 

	import java.io.*;
	import java.util.*;
	public class n02660 {
	static int N;
	static int[][] dist;
	static Vector<Integer>[] v;
	static final int INF = Integer.MAX_VALUE / 2;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	N = Integer.parseInt(br.readLine());
	v = new Vector[N + 1];
	for (int i = 0; i <= N; i++) {
	v[i] = new Vector<>();
	}
	dist = new int[N + 1][N + 1];
	for (int i = 0; i <= N; i++) {
	for (int j = 0; j <= N; j++) {
	if (i == j)
	dist[i][j] = 0;
	else
	dist[i][j] = INF;
	}
	}
	while (true) {
	String[] sarr = br.readLine().split(" ");
	int a = Integer.parseInt(sarr[0]);
	int b = Integer.parseInt(sarr[1]);
	if (a == -1 && b == -1)
	break;
	v[a].add(b);
	v[b].add(a);
	dist[a][b] = dist[b][a] = 1;
	}
	floydWarshall();
	int res = Integer.MAX_VALUE;
	int[] score = new int[N + 1];
	for (int n = 1; n <= N; n++) {
	int max = 0;
	for (int i = 1; i <= N; i++) {
	if (dist[n][i] < INF)
	max = Math.max(max, dist[n][i]);
	}
	score[n] = max;
	res = Math.min(res, score[n]);
	}
	List<Integer> list = new ArrayList<>();
	for (int n = 1; n <= N; n++) {
	if (score[n] == res)
	list.add(n);
	}
	bw.write(res + " " + list.size() + "\n");
	for (int n : list)
	bw.write(n + " ");
	bw.flush();
	}
	public static void floydWarshall() {
	for (int t = 1; t <= N; t++) {
	for (int s = 1; s <= N; s++) {
	for (int e = 1; e <= N; e++) {
	dist[s][e] = Math.min(dist[s][e], dist[s][t] + dist[t][e]);
	}
	}
	}
	}
	}

view raw 2660.java hosted with ❤ by GitHub