[백준 2610 : JAVA] 회의준비 / 플로이드 와샬 + DFS

문제

---

 

 

 

풀이

---

주어진 간선의 정보를 활용해 all-to-all 최단경로를 구한다. 플로이드 와샬을 이용해 2차원 테이블에 최단경로 비용을 저장하게 되면, 갈 수 있는 곳은 비용이 저장될테고, 갈 수 없는 곳은 INF(무한대)로 저장되어 있을텐데, 이를 활용해 그래프별로 그룹을 짓는다. 이 때, DFS를 활용한다.

 

정리하면

1. 플로이드 와샬 알고리즘을 이용해 2차원 테이블에 all-to-all 최단경로 비용을 저장한다.
2. 테이블 정보를 가지고 DFS를 통해 각 그래프별로 그룹을 나눈다.
3. 각 그룹별로 최단경로 비용이 가장 큰 값이 최소인 멤버를 찾는다.

 

 

 

코드

---

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

public class Main {

    private static final int INF = 1000000000;

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N, M, groupNumber;
    private static int[][] dist;
    private static int[] check;
    private static PriorityQueue<Integer> representation = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        check = new int[N + 1];
        dist = new int[N + 1][N + 1];

        init();

        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            dist[x][y] = dist[y][x] = 1;
        }

        floydWarshall();

        for (int i = 1; i <= N; i++) {
            if (check[i] != 0) continue;
            groupNumber++;
            dfs(i);
        }

        for (int i = 1; i <= groupNumber; i++) {
            representation.add(getGroupRepresentation(i));
        }

        print();
        br.close();
    }

    private static int getGroupRepresentation(int groupNumber) {
        int min_sum = 100007, sum, representation = 0;

        for (int i = 1; i <= N; i++) {
            if (check[i] != groupNumber) continue;
            sum = 0;
            for (int j = 1; j <= N; j++) {
                if (dist[i][j] == INF) continue;
                sum = Math.max(sum, dist[i][j]);
            }
            if (min_sum > sum) {
                min_sum = sum;
                representation = i;
            }
        }
        return representation;
    }

    private static void floydWarshall() {
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (dist[i][k] == INF || dist[k][j] == INF || i == j) continue;
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    private static void dfs(int start) {
        if (check[start] != 0) return;
        check[start] = groupNumber;

        for (int i = 1; i <= N; i++) {
            if (dist[start][i] == 0 || dist[start][i] == INF) continue;
            dfs(i);
        }
    }

    private static void print() {
        System.out.println(groupNumber);
        while (!representation.isEmpty()) {
            System.out.println(representation.poll());
        }
    }

    private static void init() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) continue;
                dist[i][j] = INF;
            }
        }
    }
}