[BOJ] 2610. 회의준비

플로이드와샬과 DFS를 같이 활용하는 문제이다.

내용자체를 이해하는데 좀 어려웠던 문제였다. 이 문제에서 결론적으로 구하는 것은 1. 서로 연결되어 있는 노드 중에서 2. 다른 노드로의  최대거리가 가장 작은 노드를 대표로 선정 하는 문제이다. 이러한 과정에서 1번을 해결하는 데에 DFS, 2번을 해결하는데 N값이 100이하이기에 플로이드와샬을 사용하였다. 전체적인 로직을 정리하자면 다음과 같다.

1. N이 100이하이기에 플로이드와샬을 이용하여 전체 노드의 최단 경로를 map[][] 에 저장
2. 1~N까지의 노드를 각각 확인하여 다른 노드로의 최대값을 maxDistanceToOther에 저장
3. 그 후 1~N까지의 노드중 방문안한 노드에 대해 graph를 이용하여 DFS
   1. DFS를 돌면서 maxDistanceToOther 값이 가장 작은 노드를 확인
   2. 그 후 PriorityQueue에 저장후 출력

package algostudy2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main_bj_2610_회의준비 {
    static int N;
    static int[][] map;
    static int[] maxDistanceToOther;
 
    static boolean[] visit;
 
    static List<Integer>[] graph;
 
    static PriorityQueue<Integer> answer;
 
    static int distance;
    static int distanceIndex;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        N = Integer.parseInt(br.readLine());
 
        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
 
        map = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                map[i][j] = (i == j) ? 0 : Integer.MAX_VALUE / 2;
            }
        }
 
        int W = Integer.parseInt(br.readLine());
        for (int i = 0; i < W; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            map[u][v] = 1;
            map[v][u] = 1;
            graph[u].add(v);
            graph[v].add(u);
        }
 
        floyd();
 
        // System.out.println(Arrays.toString(maxDistanceToOther));
 
        answer = new PriorityQueue<>();
 
        visit = new boolean[N + 1];
        for (int i = 1; i <= N; i++) {
            if (visit[i] == false) {
                distance = maxDistanceToOther[i];
                distanceIndex = i;
                dfs(i);
                // System.out.println(distance + ", " + distanceIndex);
                answer.add(distanceIndex);
            }
        }
 
        System.out.println(answer.size());
        while (!answer.isEmpty()) {
            System.out.println(answer.poll());
        }
    }
 
    static void floyd() {
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (i != j && map[i][j] > map[i][k] + map[k][j]) {
                        map[i][j] = map[i][k] + map[k][j];
                    }
                }
            }
        }
 
        maxDistanceToOther = new int[N + 1];
 
        for (int i = 1; i <= N; i++) {
            int temp = 0;
            for (int j = 1; j <= N; j++) {
                if (i == j) {
                    continue;
                }
                if (map[i][j] != Integer.MAX_VALUE / 2) {
                    temp = Math.max(temp, map[i][j]);
                }
            }
            maxDistanceToOther[i] = temp;
        }
 
    }
 
    static void dfs(int i) {
        visit[i] = true;
 
        if (distance > maxDistanceToOther[i]) {
            distance = maxDistanceToOther[i];
            distanceIndex = i;
        }
 
        for (Integer next : graph[i]) {
            if (visit[next] == false) {
                dfs(next);
            }
        }
    }
}