[BaekJoon] 2660 회장뽑기 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/2660

2.  문제

요약

• 해당 모임은 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있습니다.
• 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 됩니다.
• 예를 들어, 어느 회원이 다른 모든 회원가 친구라면, 이 회원의 점수는 1점이고, 다른 모든 회원이 친구이거나 친구의 친구라면 해당 회원의 점수는 2점이 됩니다.
• 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 두 사람은 친구사이라고 봅니다.
• 회장은 회원들 중 점수가 가장 작은 사람이 됩니다.
• 회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 문제입니다.
• 입력: 첫 번째 줄에 50 이하의 자연수인 회원의 수가 주어지고 두 번째 줄부터 한 줄에 두 개의 회원번호가 주어지는데, 이는 두 회원이 서로 친구임을 나타냅니다. 회원번호는 1부터 회원의 수만큼 붙어 있고 마지막 줄에는 -1이 두 개 들어있습니다.
• 출력: 첫 번째 줄에 회장 후보의 점수와 후보의 수를 출력하고 두 번째 줄에 회장 후보를 오름차순으로 출력합니다.

3.  소스코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int n;
	static int[][] distance;
	static final int INF = 1000000000;
	
	static void input() {
		Reader scanner = new Reader();
		n = scanner.nextInt();
		distance = new int[n + 1][n + 1];
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(i != j) {
					distance[i][j] = INF;
				}
			}
		}
		int n1, n2;
		n1 = scanner.nextInt();
		n2 = scanner.nextInt();
		while(n1 != -1 && n2 != -1) {
			distance[n1][n2] = 1;
			distance[n2][n1] = 1;
			n1 = scanner.nextInt();
			n2 = scanner.nextInt();
		}
	}
	
	static void FloydWarshall() { // 플로이드-워셜 알고리즘
		for(int i = 1; i <= n; i++) { // 정점을 1개부터 N개까지 거쳐가는 경우
			for(int j = 1; j <= n; j++) { // 정점 j에서 k로 가는 경우
				for(int k = 1; k <= n; k++) { // i번째 노드를 거쳐가는 비용이 기존 비용보다 더 작은 경우 갱신
					if(distance[j][k] > distance[j][i] + distance[i][k]) {
						distance[j][k] = distance[j][i] + distance[i][k];
					}
				}
			}
		}
	}
	
	static void solution() {
		FloydWarshall();
		int[] each_distance = new int[n + 1];
		int min = INF;
		for(int i = 1; i <= n; i++) {
			int dis = 0;
			for(int j = 1; j <= n; j++) {
				if(distance[i][j] != INF) {
					dis = Math.max(dis, distance[i][j]);
				}
			}
			each_distance[i] = dis;
			min = Math.min(min, dis);
		}
		ArrayList<Integer> candidate = new ArrayList<Integer>();
		for(int i = 1; i <= n; i++) {
			if(min == each_distance[i]) {
				candidate.add(i);
			}
		}
		sb.append(min + " " + candidate.size());
		sb.append("\n");
		for(int c : candidate) {
			sb.append(c + " ");
		}
		sb.append("\n");
	}
	
	public static void main(String[] args) {
		input();
		solution();
		System.out.println(sb.toString());
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4.  접근

• 해당 문제는 플로이드–워셜(Floyd Warshall) 알고리즘을 이용하여 해결할 수 있습니다.

플로이드-워셜(Floyd Warshall)

• 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘입니다.
• 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있습니다.
• 모든 노드 간의 최단거리를 구하는 알고리즘이므로 2차원 행렬을 구성합니다.
• 2차원 행열을 구성할 때는 처음에는 연결되어있는 노드 사이에는 해당 가중치를, 본인 노드에는 0을, 연결되어있지 않은 노드들에는 최댓값으로 지정해줍니다.
• 플로이드-워셜 알고리즘은 모든 정점에서 다른 모든 정점으로 가는 최소 비용을 단계적으로 갱신하며 진행하는 알고리즘입니다.
• 간선을 0개 거친 경우, 간선을 1개 거친 경우, ..., 간선을 N개(정점의 개수) 거친 경우의 최소 거리 비용을 비교하면서 위에서 정의한 2차원 행렬을 갱신합니다.

구현

• 주어진 연결관계를 2차원 배열 distance에 설정합니다.
• distance에 대해 플로이드-워셜 알고리즘을 적용하여 모든 정점에서 다른 모든 정점으로 가는 최단 경로를 구합니다.
• distance에는 각 정점으로 가는 최소 경로가 들어가있는데, 각 정점에 대해서 다른 정점까지의 최단 경로 중 가장 큰 값이 각 정점에 대한 이 문제에서의 점수가 됩니다.
• 이를 구하여 each_distance라는 1차원 배열에 넣어줍니다.
• each_distance 배열에서 최솟값을 찾아 해당 점수를 갖는 회장 후보들을 찾고 이를 출력합니다.