[백준 2610] 회의준비 (Java)

이 문제에서 말장난은  '대표에게 의견을 전달하는 경로가 여러 개 있을 경우에는 가장 적은 사람을 거치는 경로로 의견을 전달하며 이때 거치는 사람의 수를 참석자의 의사전달시간이라고 한다.' 인 것 같다.

의사전달 != i번째 노드가 같은 위원회에 속한 다른 노드까지 도달하는 경로의 합
의사전달 == i번째 노드가 같은 위원회에 속한 다른 노드까지 도달하는 경로 중 가장 큰 수

 

즉, 문제의 예시로 설명을 들자면 잘못된 의사결정과 정답인 의사결정의 결과를 표로 표시하면 아래와 같다.

	1	2	3	4	5	6	7	8	틀린 의사결정
1	-	1	2	∞	∞	∞	∞	∞	3
2	1	-	1	∞	∞	∞	∞	∞	2
3	2	1	-	∞	∞	∞	∞	∞	3
4	∞	∞	∞	-	1	1	1	∞	3
5	∞	∞	∞	1	-	1	2	∞	4
6	∞	∞	∞	1	1	-	1	∞	3
7	∞	∞	∞	1	2	1	-	∞	4
8	∞	∞	∞	∞	∞	∞	∞	∞	∞

 

 

	1	2	3	4	5	6	7	8	정답인 의사결정
1	-	1	2	∞	∞	∞	∞	∞	2
2	1	-	1	∞	∞	∞	∞	∞	1
3	2	1	-	∞	∞	∞	∞	∞	1
4	∞	∞	∞	-	1	1	1	∞	1
5	∞	∞	∞	1	-	1	2	∞	2
6	∞	∞	∞	1	1	-	1	∞	1
7	∞	∞	∞	1	2	1	-	∞	2
8	∞	∞	∞	∞	∞	∞	∞	-	∞

 

 

- JAVA

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;
 
public class Main{
    static int INF = 987654321;
    static boolean[] visited = new boolean[102];
    static int[][] arr = new int[102][102];
    static int[] ans = new int[102];
    static int n=0, m=0;
    static Queue<Integer> q = new LinkedList<Integer>();
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
 
        // 초기화
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++)
                arr[i][j] = INF;
        }
 
        // 입력받기
        StringTokenizer st; int from=0, to=0;
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine(), " ");
 
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
 
            arr[from][to]=1;
            arr[to][from]=1;
        }
 
        // 플로이드 와샬 알고리즘
        for(int k=1; k<=n; k++){
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    arr[i][j] = Math.min(arr[i][j], arr[i][k]+arr[k][j]);
                }
            }
        }
 
        // 각 사이클 (같은 위원회)에서 대표 뽑기
       int temp=0, cnt=0;
        for(int i=1; i<=n; i++){
            if(visited[i] == false){
                ans[cnt] = count(i);
                cnt++;
            }
        }
 
        // 대표 번호가 작은순이니 정렬
        Arrays.sort(ans, 0, cnt);
        
        // 출력
        StringBuilder sb = new StringBuilder();
        sb.append(cnt).append("\n");
        for(int i=0; i<cnt; i++)
            sb.append(ans[i]).append("\n");
        
        System.out.println(sb);
    }
 
    public static int count(int num){
        q.add(num);
 
        // rp = 대표 번호, maxNum = 각 노드에서 가장 큰 수(몇 다리를 건너야 하는지)
        int rp = 987654321, maxNum = 987654321;
 
        while(!q.isEmpty()){
            int node = q.peek(); q.remove();
            int temp = -1; 
 
            if(visited[node]) continue;
            else {
                visited[node] = true;
                for(int i=1; i<=n; i++){
                    if(node == i) continue;
                    if(arr[node][i] != INF){
                        q.add(i);
                        temp = (temp < arr[node][i]) ? arr[node][i] : temp;
                    }
                }
            }
 
            if(temp < maxNum){
                rp = node;
                maxNum = temp;
            }
        }
        
        return rp;
    }
}