[백준] 2610번. 회의준비(JAVA)

문제

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

---

풀이(39분)

import java.io.*;
import java.util.*;

public class Main {

    // union-find를 통해 위원회 수 및 속한 인원을 구한다
    // floyd 행렬 내에서 의견 전달 시간의 최솟값을 구한다.
    // 만약 동일한 시간을 갖는 대표가 있다면 한명이면 된다.
    // 이 최솟값을 만들 수 있는 사람이 그 위원회의 대표가 된다.
    // 이 인덱스를 List에 넣고, 오름차순으로 출력한다.

    static int n; // 회의에 참석하는 사람의 수
    static int[] union; // 위원회
    static int[][] floyd; // 최단 거리
    static List<Integer> unionMasters = new ArrayList<>(); // 조합 대표들의 모임
    static final int INF = 101; // 최대 거리

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder(); // 정답 출력을 위함

        n = Integer.parseInt(br.readLine()); // 사람의 수

        union = new int[n+1];
        for(int i = 0; i <= n; i++){
            union[i] = i; // 초기 자신 혼자의 그룹 체크
        }

        int m = Integer.parseInt(br.readLine()); // 관계의 수

        floyd = new int[n+1][n+1]; // 인덱스를 위한 +1 초기화

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(i == j){ // 자기 자신의 거리는 0
                    floyd[i][j] = 0;
                    continue;
                }
                floyd[i][j] = INF; // 관계가 없는 경우 최대값으로 초기화
            }
        }


        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int first = Integer.parseInt(st.nextToken()); // 입력 첫 번째
            int second = Integer.parseInt(st.nextToken()); // 입력 두 번쨰
            floyd[first][second] = 1;
            floyd[second][first] = 1; // 양방향 연결 체크
            union(first, second); // 두 사람의 조합을 연결
        }

        floyd(); // 모든 사람들 간의 관계에 대한 비용 체크

        // 키 : 조합 번호
        // 밸류 : 조합에 속한 사람들의 번호
        HashMap<Integer, List<Integer>> unionMembersMap = new HashMap<>();

        // union[] -> unionMembersMap 로 전환
        for(int i = 1; i <= n; i++){
            unionMembersMap.computeIfAbsent(union[i], k -> new ArrayList<>()).add(i);
        }

        sb.append(unionMembersMap.keySet().size()).append("\n"); // 구성되는 위원회의 수

        // 키셋에 대해 반복
        for(int i : unionMembersMap.keySet()){
            findUnionMasters(unionMembersMap.get(i)); // 리스트를 메서드에 던짐
        }

        // 리스트 정렬(오름차순)
        Collections.sort(unionMasters);
        for(int i : unionMasters){
            sb.append(i).append("\n"); // 조합 대표
        }

        System.out.println(sb);

    }

    static void union(int first, int second){
        int temp = Math.min(first, second); // 값이 작은 인덱스 기준
        if(temp != first){
            second = first;
            first = temp;
        } // 2번째 매개변수로 들어온게 더 큰 경우 first <-> second 교체

        int changeFlag = union[second];
        union[second] = union[first];
        for(int i = 1; i <= n; i++){
            if(union[i] == changeFlag){ // 해당했던 조합원 모두 조합 변경
                union[i] = union[first];
            }
        }
    }

    // 플로이드 - 와샬 알고리즘
    static void floyd(){
        for(int k = 1; k<= n; k++){
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    floyd[i][j] = Math.min(floyd[i][j], floyd[i][k] + floyd[k][j]); // 경로 계산
                }
            }
        }
    }

    /**
     * 조합 내에서 대표를 누구로 할 것인지 찾아주는 메서드
     * @param list 한 조합 내의 조합원 리스트
     */
    static void findUnionMasters(List<Integer> list){
        int count = INF; // 최초 값 최대
        int idx = list.get(0); // 인덱스 0번으로 대표 임의 초기화
        for(int i = 0; i < list.size(); i++){
            int temp = 0; // 현 대표로부터 최대 거리
            int master = list.get(i); // 대표의 번호
            for(int j = 0; j < list.size(); j++){
                temp = Math.max(temp, floyd[list.get(j)][master]); // 합이 아닌 단순 거리

            }
            if(temp <= count){ // 만약 대표가 될 수 있다면
                idx = master; // idx에 대표 번호
                count = temp; // count 값 변경
            }
        }
        unionMasters.add(idx); // 리스트에 추가
    }

}

---

문제 풀이 전략

 

문제 이해 자체가 매우 중요하다.

• 서로 알고 있는 사람은 반드시 같은 위원회에 속해야 한다.
  • 이런 조건이 주어지면 꼭 입력을 함께 살펴보자.
    • 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이어 M개의 각 줄에는 서로 아는 사이인 참석자를 나타내는 두 개의 자연수가 주어진다.
  • 입력을 보면 알 수 있는 부분은 a → b의 단방향 관계가 아닌 a ↔ b의 양방향 관계다.
• 효율적인 회의 진행을 위해 위원회의 수는 최대가 되어야 한다.
  • 알고 있는 관계가 아니라면 최대한 분리 시켜 위원회의 수를 최대로 만들자.
• 대표만이 회의 시간 중 발언권을 갖는다.
  • 타 인원은 자신이 속한 위원회의 대표에게 자신의 의견을 전달해야 한다.
  • 대표에게 의견을 전하기까지 여러 사람을 거칠 수 있다.
    • 입력을 살펴보자.
      • 인원과 인원 사이의 별도 비용이 존재하지 않는다.(모두 1로 가정)
  • 모든 참석자들의 의사전달시간 중 최댓값이 최소가 되도록 대표를 정하라.
  • 1,2,3번으로 구성된 위원회에서 1↔2 , 2↔3이라면 2가 대표가 된다. 이때의 의사 전달시간은 1이다.
    • 여기서 알 수 있는 것이 대표라는 사람은 중간에 위치한 것이 좋다는 뜻이다!
    • 착각하기 쉬운게 총 의사전달시간으로 따지면 동일한 값이 나올 수도 있다.
      • 최적의 인원의 총 의사전달시간이 답이 아니라는 뜻이다.

서로 알고 있는 사람은 반드시 같은 위원회에 속해야 한다.

1. 서로 알고 있는 사람을 같은 위원회에 속하게 하자.
2. 서로 다른 위원회에 속한 사람이 서로 알고 있다면, 하나의 위원회로 합쳐야 한다.

union-find 알고리즘을 응용하여 구하자.

2024.12.04 - [문제 풀이/도구정리] - [도구정리] Union-Find 알고리즘

[도구정리] Union-Find 알고리즘

 

모든 사람 간의 의사 전달 시간을 구하자.

1. a라는 사람이 의견을 전달할 수 있는 b가 있다면, 반드시 a와 b는 같은 그룹이다.
2. 따라서, 모든 사람들 간의 의사 전달 시간을 구해두자.
3. 이 때 의사 전달이 불가능하다면 101(최대 100명으로 99가 최댓값임)을 설정하자.

각 사람에 대한 모든 사람의 거리이고, n = 100이 최대이므로 플로이드-와샬 알고리즘을 활용하자.

2025.04.01 - [문제 풀이/도구정리] - [도구정리] 플로이드-와샬(Floyd-Warshall) 알고리즘

[도구정리] 플로이드-와샬(Floyd-Warshall) 알고리즘

 

각 위원회마다 대표를 선정하자

1. 위원회에 있는 모든 인물이 대표가 되었을 때 최대 의사 전달 시간이 얼마인지 구하자.
2. 이 값이 가장 작은 사람이 대표가 되어야 한다.