[백준] 2610번 : 회의준비 - 자바(JAVA)

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

2610번: 회의준비

 

문제 해석

위원회를 구성하려고 하는데 위원회를 구성하는 방식은 다음과 같습니다

• 1. 서로 알고 있는 사람은 반드시 같은 위원회에 속해야 합니다.
• 2. 효율적인 회의 진행을 위해 위원회의 수는 최대가 되어야 합니다.

이후에 각 위원회의 대표를 한 명씩 뽑아 대표만이 회의 시간 중 발언권을 가질 수 있습니다.

회의 참석자들은 자신의 의견을 말하기 위해서는 자신이 속한 위원회의 대표에게 의견을 전달해야 합니다.

 

그런데 참석자는 자신이 알고 있는 사람들에게만 의견을 전달할 수 있어 대표에게 의견을 전달하기 위해서는 때로 여러 사람을 거쳐야 합니다.

만약 의견을 전달하는 경로가 여러 개 있는 경우에는 가장 적은 사람을 거치는 경로로 의견을 전달하며 이때 거치는 사람의 수를 참석자의 의사전달시간이라고 합니다.

 

위원회의 모든 참석자들의 의사전달시간 중 최댓값이 최소가 되도록 대표를 정하는 프로그램을 작성하시오.

 

문제 풀이 전 설계

8
7
1 2
2 3
4 5
5 6
4 6
6 7
7 4

예제 입력이 다음과 같이 주어졌을 때 그래프를 그려보겠습니다.

3개의 그래프가 구성되며 각각의 위원회의 대표로는 2, 4, 8입니다.

따라서 3 2 4 8 이 정답입니다.

이때 4 말고 6도 가능하지만 대표 번호가 작은 순으로 출력하는 것으로 가정하겠습니다.

 

서로 알고 있는 사람을 양방향 그래프로 표현할 수 있습니다.

의견을 전달하는 과정을 길 찾기 과정으로 생각하고 최단거리를 찾기 위해서 (어떤 사람 -> 대표)로 가는 최단거리를 다익스트라를 통해서 구합니다.

 

이후에 한사람씩 대표를 돌아가면서 하며 최솟값을 갱신하면서 정답을 구해나갑니다.

 

그리고 중요한 포인트가 대표자를 기준으로 의사결정시간이 최소가 되는 것을 고르는 문제가 아닙니다.

 

그룹원에서 대표자를 선정합니다.

그룹원들과의 거리를 측정해서 거기서 가장 먼 거리를 임시로 가지고 있습니다.

모든 그룹원들이 대표자를 해보고 그때 이 값이 가장 최소로 가지는 사람이 대표자가 되어야 합니다.

위의 그림을 예를 들어 보겠습니다

4번을 선정하게 되면 의사 결정하는 데 걸리는 시간은 10초입니다. (모든 구성원을 더했을 때)

3번을 선정하게 되면 의사결정하는데 걸리는 시간은 13초입니다.

 

하지만 이것으로 4번을 선정하면 안됩니다.

 

4번의 경우는 의사 결정하는 데 걸리는 시간의 최대가 3초입니다. (4 - 1 과의 거리)

3번의 경우는 의사결정하는데 걸리는 시간의 최대가 2초입니다. (3과 1,5,6,7,8,9 거리의 최대는 2)

 

따라서 3번을 선정해야 합니다.

 

 

1. DFS로 그래프를 구분한다.

2. 그래프 별로 최솟값을 탐색한다. ( 다익스트라 또는 플로이드 와샬 알고리즘 사용)

3. 그룹별로 값을 찾아 넣는다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main_2610_회의준비 {

    static boolean[] visited;
    static int N,M;
    static int[][] DP,graph;
    static List<Integer> groups;
    static final int INF = 10_000_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        graph = new int[N+1][N+1];
        DP = new int[N+1][N+1];

        M = Integer.parseInt(br.readLine());
        StringTokenizer st = null;
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine()," ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            DP[from][to] = DP[to][from] = 1;
            graph[from][to] = graph[to][from] = 1;
        }
        //입력 끝

        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                if(i==j) continue;
                if(DP[i][j] == 0) DP[i][j] = INF;
            }
        }

        //플로이드 워샬
        for(int node=1; node<=N; node++){
            for(int i=1; i<=N; i++){
                for(int j=1; j<=N; j++){
                    DP[i][j] = Math.min(DP[i][j], DP[i][node] + DP[node][j]);
                }
            }
        }


        
        List<Integer> result = new ArrayList<>();
        int groupCount = 0;
        int minNode = 0,curTime;
        
        groups = new ArrayList<>();
        visited = new boolean[N+1];
        //그룹 찾기
        for(int i=1; i<=N; i++){
            if(visited[i]){
                continue;
            }
            curTime =Integer.MAX_VALUE;

            visited[i] = true;
            groups.add(i);
            DFS(i);

            //그룹이 형성됨
            for(int j=0; j<groups.size(); j++){
                //대표자 선정
                int delegate = groups.get(j);
                int maxTime = 0;
                for(int k=1; k<=N; k++){
                    //그룹원이 아니면 체크 x
                    if(!groups.contains(k)){
                        continue;
                    }

                    //의사결정시간이 최대인 경우가 최소가 되도록
                    maxTime = Math.max(maxTime, DP[k][delegate]);

                }
                //갱신발생
                if(curTime > maxTime){
                    minNode = delegate;
                    curTime = maxTime;
                }
            }


            groups.clear();
            groupCount++;
            result.add(minNode);
        }

        Collections.sort(result);
        result.add(0,groupCount);

        StringBuilder sb = new StringBuilder();
        for(Integer e: result){
            sb.append(e + "\n");
        }

        System.out.print(sb.toString());


    }

    private static void DFS(int currentNode) {
        for(int i=1; i<=N; i++) {
            //방문된 경우
            if (visited[i]) {
                continue;
            }
            //갈 수 없는 경우
            if(graph[currentNode][i] == 0){
                continue;
            }
            visited[i] = true;
            groups.add(i);
            DFS(i);
        }
    }
}