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

문제

KOI 준비를 위해 회의를 개최하려 한다. 주최측에서는 회의에 참석하는 사람의 수와 참석자들 사이의 관계를 따져 하나 이상의 위원회를 구성하려고 한다. 위원회를 구성하는 방식은 다음과 같다.

 

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

 

이런 방식으로 위원회를 구성한 후에 각 위원회의 대표를 한 명씩 뽑아야 한다. 각 위원회의 대표만이 회의 시간 중 발언권을 가지며, 따라서 회의 참석자들이 자신의 의견을 말하기 위해서는 자신이 속한 위원회의 대표에게 자신의 의견을 전달해야 한다.

 

그런데 각 참석자는 자신이 알고 있는 사람에게만 의견을 전달할 수 있어 대표에게 의견을 전달하기 위해서는 때로 여러 사람을 거쳐야 한다. 대표에게 의견을 전달하는 경로가 여러 개 있을 경우에는 가장 적은 사람을 거치는 경로로 의견을 전달하며 이때 거치는 사람의 수를 참석자의 의사전달시간이라고 한다.

 

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

 

예를 들어 1번, 2번, 3번 세 사람으로 구성되어 있는 위원회에서 1번과 2번, 2번과 3번이 서로 알고 있다고 하자. 1번이 대표가 되면 3번이 대표인 1번에게 의견을 전달하기 위해서 2번을 거쳐야만 한다.

 

반대로 3번이 대표가 되어도 1번이 대표인 3번에게 의견을 전달하려면 2번을 거쳐야만 한다. 하지만 2번이 대표가 되면 1번과 3번 둘 다 아무도 거치지 않고 대표에게 직접 의견을 전달 할 수 있다. 따라서 이와 같은 경우 2번이 대표가 되어야 한다.

 

 

입력

첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이어 M개의 각 줄에는 서로 아는 사이인 참석자를 나타내는 두개의 자연수가 주어진다.

 

 

출력

첫째 줄에는 구성되는 위원회의 수 K를 출력한다. 다음 K줄에는 각 위원회의 대표 번호를 작은 수부터 차례로 한 줄에 하나씩 출력한다. 한 위원회의 대표가 될 수 있는 사람이 둘 이상일 경우 그중 한 명만 출력하면 된다.

 

 

풀이

BFS와 플로이드 와샬 알고리즘을 적절히 섞어서 풀 수 있는 문제였습니다.

 

문제에서는 특정 집합을 묶고, 그 안에서 리더를 뽑아내는 것을 요구하였습니다.

특정 집합을 묶는 과정에서 BFS를, 리더를 뽑아내는 과정을 플로이드 와샬 알고리즘을 사용하면 됩니다.

 

문제의 예시를 보면서 설명해 보겠습니다.

 

<문제의 입력값>

 

1 2

2 3

4 5

5 6

4 6

6 7

7 4

 

위의 과정에서 집합을 묶기 위해서는 인접행렬이나 인접리스트를 사용해야하는데, N이 최대 100으로 작은 수이기때문에 양방향 인접행렬을 구현합니다.

 

그리고 전형적인 BFS를 사용하면 아래와 같이 3개의 집합으로 나뉩니다.

 

 

 

 

문제에서는 의사 전달 시간의 최댓값이 최소인 인덱스를 찾으라고 하였습니다.

그렇다면, 모든 정점에 대해서 모든 정점 사이의 최단거리를 구해 놓고, 각 인덱스마다 의사 전달 시간의 최댓값을 비교하면 됩니다.

 

위 그래프에서 (1, 2, 3) 집합을 플로이드 와샬 알고리즘을 수행하면 다음과 같이 값이 초기화가 됩니다.

 

 

	1	2	3
1	0	1	2
2	1	0	1
3	2	1	0

 

 

1과 3의 최대 의사 전달시간은 2인데 반해, 2의 최대 의사 전달 시간은 1입니다.

 

따라서 (1, 2, 3) 집합의 리더는 2가 되는 것입니다.

 

위와 같은 과정으로 나머지 2개의 집합에 대해서도 리더를 구한 뒤, 총 리더의 개수와 리더의 명단을 쭉 나열하면 됩니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static int N;
    static final int INF = 987654321;
    static int[][] arr;
    static boolean[] visited;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
 
        arr = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i != j) {
                    arr[i][j] = INF;
                }
            }
        }
        
        // 양방향 인접행렬 구현
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
 
            arr[x][y] = arr[y][x] = 1;
        }
 
        visited = new boolean[N + 1];
        
        ArrayList<Integer> readerList = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                readerList.add(findReader(i));
            }
        }
        
        // 리더의 수와 리더 명단 출력.
        StringBuilder sb = new StringBuilder();
        sb.append(readerList.size() + "\n");
 
        Collections.sort(readerList);
        for (int i = 0; i < readerList.size(); i++) {
            sb.append(readerList.get(i) + "\n");
        }
 
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
 
    public static int findReader(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
 
        visited[start] = true;
        
        ArrayList<Integer> arrList = new ArrayList<>(); // start와 연결된 집합
        arrList.add(start);
    
        // BFS 알고리즘 
        while (!q.isEmpty()) {
            int now = q.poll();
 
            for (int i = 1; i <= N; i++) {
                if (arr[now][i] != INF && !visited[i]) {
                    visited[i] = true;
                    q.offer(i);
                    arrList.add(i);
                }
            }
        }
        
        // 의사 전달 시간을 기준으로 플로이드 와샬 알고리즘 수행
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (arr[i][j] > arr[i][k] + arr[k][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }
 
        int idx = -1;
        int res = INF;
 
        for (int i = 1; i <= N; i++) {
            if (!arrList.contains(i)) {
                continue;
            }
 
            int total = 0;
            for (int j = 1; j <= N; j++) {
                if (!arrList.contains(j)) {
                    continue;
                }
 
                total = Math.max(total, arr[i][j]);
            }
            
            // 의사 전달 시간의 최댓값이 최소인 인덱스를 찾아야 함.
            if (res > total) {
                res = total;
                idx = i;
            }
        }
 
        return idx;
    }
 
}
 

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.