[BOJ] 2610. 회의 준비

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

접근 방법

처음에는 문제 풀이 방법과 질문에 Floyd에 관한 내용 밖에 없어서

Floyd로 사용해서 풀려고 노력했었지만 BFS로 푸는 게 더 직관적이었기 때문에 BFS로 풀게 되었다.

먼저 그룹을 연관되어있는 사람들 끼리 나눈 후

그룹별로 의사전달시간 중 최댓값이 최소가 되도록 대표가 되도록 코드를 짰다.

Need Know

1. BFS

전체 코드 ( Java )

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int M;
    static Long[][] relation;
    static boolean[] visit;
    static Queue<Integer> queue;
    static Queue<time> timeQueue;
    static ArrayList<Integer>[] group;
    static int[][] ans;

    public static void main(String[] args) throws IOException {
        set();
        solve();

        bw.flush();
        bw.close();
        br.close();
    }

    static void set() throws IOException {
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        relation = new Long[N+1][N+1];
        for(int i=1; i<N+1; i++){
            for(int k=1; k<N+1; k++){
                relation[i][k] = Long.valueOf(Integer.MAX_VALUE);
            }
        }
        visit = new boolean[N+1];
        group = new ArrayList[N+1];
        for(int i=1; i<N+1; i++){
            group[i] = new ArrayList<>();
        }
        for(int i=0; i<M;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            relation[a][b] = Long.valueOf(1);
            relation[b][a] = Long.valueOf(1);
        }
    }

    static void solve() throws IOException {
        int groupNumber = getGroupNum();
        bw.write(groupNumber +"\n");
        ans = new int[groupNumber+1][N+1];
        getGroupPresent(groupNumber);
        int[] realAnswer = new int[groupNumber+1];
        for(int i=1; i<=groupNumber; i++){
            int temp = Integer.MAX_VALUE;
            for(int k=0; k<group[i].size(); k++){
                if(temp > ans[i][group[i].get(k)]){
                    temp = ans[i][group[i].get(k)];
                    realAnswer[i] = group[i].get(k);
                }
            }
        }
        Arrays.sort(realAnswer);
        for(int i=1; i<=groupNumber; i++){
            bw.write(realAnswer[i] +"\n");
        }
    }
    static int getGroupNum(){
        int groupNum = 0;
        for(int i=1; i<N+1; i++){
            if(!visit[i]){
                groupNum++;
                queue = new LinkedList<>();
                queue.add(i);
                group[groupNum].add(i);
                visit[i] = true;
                while(!queue.isEmpty()){
                    int now = queue.poll();
                    for(int k=1; k<N+1; k++){
                        if(relation[now][k] == 1 && !visit[k]){
                            visit[k] = true;
                            queue.add(k);
                            group[groupNum].add(k);
                        }
                    }
                }
            }
        }
        return groupNum;
    }
    static void getGroupPresent(int groupNumber){
        for(int groups = 1; groups <= groupNumber; groups++){

//            System.out.println("group member is ");
//
//            for(int i=0; i<group[groups].size(); i++){
//                System.out.print( group[groups].get(i) +" ");
//            }
//            System.out.println();

            for(int i=0; i<group[groups].size(); i++){
                int timeLimit = 0;
                if(group[groups].size() == 1){
                    timeLimit = -1;
                }else{
                    timeQueue = new LinkedList<>();
                    visit = new boolean[N+1];
                    visit[group[groups].get(i)] = true;
                    timeQueue.add(new time(group[groups].get(i), 0));
                    while(!timeQueue.isEmpty()){
                        time now = timeQueue.poll();
                        if(timeLimit < now.times){
                            timeLimit = now.times;
                        }
                        for(int k=1; k<N+1; k++){
                            if(relation[now.index][k] == 1 && !visit[k]){
                                visit[k] =true;
                                timeQueue.add(new time(k, now.times+1));
                            }
                        }
                    }
                }
//                System.out.println("when group number is  " + group[groups].get(i) +" time is " + timeLimit);
                ans[groups][group[groups].get(i)] = timeLimit;

            }
        }
    }
}
class time{
    int index, times;

    public time(int index, int times) {
        this.index = index;
        this.times = times;
    }
}