[BaekJoon] 2610 회의준비 (Java)

1.  문제 링크

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

2.  문제

요약

• 주최측에서는 회의에 참석하는 사람의 수와 참석자들 사이의 관계를 따져 하나 이상의 위원회를 구성하려고 합니다.
• 위원회를 구성하는 방식은 다음과 같습니다.
  1. 서로 알고 있는 사람은 반드시 같은 위원회에 속해야 합니다.
  2. 효율적인 회의 진행을 위해 위원회의 수는 최대가 되어야 합니다.
• 위와 같은 방식으로 위원회를 구성한 후에 각 위원회의 대표를 한 명씩 뽑아야 하는데, 회의 참석자들이 자신의 의견을 말하기 위해서 자신이 속한 위원회의 대표에게 자신의 의견을 전달해야 합니다.
• 각 참석자는 자신이 알고 있는 사람에게만 의견을 전달할 수 있어 대표에게 의견을 전달하기 위해서는 여러 사람을 거쳐야 할 수도 있습니다.
• 대표에게 의견을 전달하는 경로가 여러 개 있을 경우, 가장 적은 사람을 거치는 경로로 의견을 전달하며, 이 때 거치는 사람의 수를 참석자의 의사전달시간이라고 합니다.
• 위원회에서 모든 참석자들의 의사전달시간 중 최댓값이 최소가 되도록 대표를 정하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100보다 작거나 같은 자연수인 회의에 참석하는 사람의 수 N이 주어지고 두 번째 줄에 서로 알고 있는 관계의 수 M이 주어지며 세 번째 줄부터 M개의 줄에 서로 아는 사이인 참석자를 나타내는 두 자연수가 주어집니다.
  • 참석자들은 1부터 N까지의 자연수로 표현됩니다.
• 출력: 첫 번째 줄에 구성되는 위원회의 수 K를 출력합니다. 두 번째 줄부터 K개의 줄에 각 위원회의 대표 번호를 작은 수부터 차례로 출력합니다. 한 위원회의 대표가 될 수 있는 사람이 둘 이상일 경우 그 중 한 명만 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static HashMap<Integer, ArrayList<Integer>> relationList, map;
    static int[][] relationArr;
    static ArrayList<ArrayList<Integer>> committees;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        relationArr = new int[N + 1][N + 1];
        relationList = new HashMap<>();
        for(int attendee = 1; attendee <= N; attendee++) {
            relationList.put(attendee, new ArrayList<>());
            Arrays.fill(relationArr[attendee], Integer.MAX_VALUE);
            relationArr[attendee][attendee] = 0;
        }

        int relationNum = scanner.nextInt();
        for(int idx = 0; idx < relationNum; idx++) {
            int attendee1 = scanner.nextInt(), attendee2 = scanner.nextInt();

            relationList.get(attendee1).add(attendee2);
            relationList.get(attendee2).add(attendee1);

            relationArr[attendee1][attendee2] = 1;
            relationArr[attendee2][attendee1] = 1;
        }
    }

    static void solution() {
        StringBuilder sb = new StringBuilder();

        makeCommittee();
        sb.append(committees.size()).append('\n');

        ArrayList<Integer> representatives = new ArrayList<>();

        for(ArrayList<Integer> committee : committees) {
            if(committee.size() == 1) {
                representatives.add(committee.get(0));
                continue;
            }

            floydWarshall(committee);
            representatives.add(findRepresentative(committee));
        }

        Collections.sort(representatives);
        for(int representative : representatives) sb.append(representative).append('\n');

        System.out.print(sb);
    }

    static int findRepresentative(ArrayList<Integer> committee) {
        int min = Integer.MAX_VALUE, selectedRepresentative = 0;

        for(int representative : committee) {
            int max = Integer.MIN_VALUE;
            for(int attendee : committee) {
                if(representative == attendee) continue;
                max = Math.max(max, relationArr[representative][attendee]);
            }

            if(max < min) {
                min = max;
                selectedRepresentative = representative;
            }
        }

        return selectedRepresentative;
    }

    static void floydWarshall(ArrayList<Integer> committee) {
        for(int middle = 0; middle < committee.size(); middle++) {
            int middleAttendee = committee.get(middle);
            for(int start = 0; start < committee.size(); start++) {
                int startAttendee = committee.get(start);
                for(int end = 0; end < committee.size(); end++) {
                    if(start == end || start == middle || end == middle) continue;

                    int endAttendee = committee.get(end);

                    if(relationArr[startAttendee][middleAttendee] == Integer.MAX_VALUE
                            || relationArr[middleAttendee][endAttendee] == Integer.MAX_VALUE) continue;

                    if(relationArr[startAttendee][endAttendee] > relationArr[startAttendee][middleAttendee] + relationArr[middleAttendee][endAttendee])
                        relationArr[startAttendee][endAttendee] = relationArr[startAttendee][middleAttendee] + relationArr[middleAttendee][endAttendee];
                }
            }
        }
    }

    static void makeCommittee() {
        boolean[] visited = new boolean[N + 1];
        committees = new ArrayList<>();

        for(int attendee = 1; attendee <= N; attendee++) {
            ArrayList<Integer> list = new ArrayList<>();
            if(!visited[attendee]) {
                visited[attendee] = true;
                list.add(attendee);
                dfs(attendee, visited, list);
                committees.add(list);
            }
        }
    }

    static void dfs(int attendee, boolean[] visited, ArrayList<Integer> list) {
        for(int next : relationList.get(attendee)) {
            if(!visited[next]) {
                visited[next] = true;
                list.add(next);
                dfs(next, visited, list);
            }
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    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) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}