[백준] 2660 회장뽑기

문제 출처: https://www.acmicpc.net/problem/2660

2660번: 회장뽑기

 

1. 입력

: 첫째 줄에 트리의 노드의 개수 N이 주어진다.

: N은 50보다 작거나 같은 자연수이다.

: 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다.

: 만약 부모가 없다면 (루트) -1이 주어진다.

: 셋째 줄에는 지울 노드의 번호가 주어진다.

 

2. 출력

: 첫째 줄에는 회장 후보의 점수와 후보의 수를 출력하고, 두 번째 줄에는 회장 후보를 오름차순으로 모두 출력한다.

 

3. 풀이

: 플로이드-와샬 알고리즘을 사용해 풀 수 있다.

: 친구와 나와 A라는 사람의 관계를 파악할 때 두 가지 경우로 나눠볼 수 있다.

1) 나와 A가 직접적으로 친구가 아닐 때

→ 중간에 다른 사람 B을 거쳐 갈 수 있다면 그 사이의 관계는 나와 B와의 관계 + B와 A와의 관계로 표현 가능하다

2) 나와 A가 관계가 있을 때

→ 문제에서 친구의 친구와 친구 관계가 둘 다 성립할 경우 친구로 간주하기 때문에 직접적인 관계와 1)번에서 더한 관계 중 더 가까운 관계를 저장한다.

 

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	public static void main(String[] args) throws Exception{
		int N = Integer.parseInt(br.readLine());
		int[][] adj = new int[N+1][N+1];
		
		while(true) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			if(v1 == -1 && v2 == -1) break;
			
			adj[v1][v2] = 1;
			adj[v2][v1] = 1;
		}
		

		for(int j = 1; j < N+1; j++) {
			for(int i = 1; i < N+1; i++) {
				if(i == j) continue;
				for(int k = 1; k < N+1; k++) {
					if(i == k || j == k) continue;
					if(adj[i][j] != 0 && adj[j][k] != 0) {
						if(adj[i][k] == 0)adj[i][k] = adj[i][j]+adj[j][k];
						else adj[i][k] = Math.min(adj[i][k], adj[i][j]+adj[j][k]);
					}
				}
			}
		}
		
		int ans = Integer.MAX_VALUE;
		int[] arr = new int[N+1];
		
		for(int i = 1; i < N+1; i++) {
			int res = 0;
			for(int j = 1; j < N+1; j++) {
				if(i == j)continue;
				if(adj[i][j] == 0) {
					res = 0;
					break;
				}
				res = Math.max(res, adj[i][j]);
			}
			arr[i] = res;
			if(res < ans) ans = res;
		}
		ArrayList<Integer> list = new ArrayList<>();
		for(int i = 1; i <N+1; i++ ) {
			if(ans == arr[i])list.add(i);
		}
		
		sb.append(ans + " " + list.size()+"\n");
		for(int num : list) sb.append(num + " ");
		System.out.println(sb);
		
	}
}