[BOJ] 백준 2610 회의준비

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

 Input 

8

7

1 2

2 3

4 5

5 6

4 6

6 7

7 4

 

 Output 

3
2
4
8

첫째 줄에 구성되는 위원회의 수 K

그 다음 K줄에는 각 위원회의 대표 번호를 오름차순 출력

※ 한 위원회의 대표가 될 수 있는 사람이 둘 이상일 경우, 그중 한 명만 출력

결과 설명

　

- 위원회는 총 3개로 구분.

- 대표는 각 연결 그래프에서 거리비용이 제일 작은 정점이며,

  정점 [4], [6]이 대표가 될 수 있지만, 그 중 한개 출력

- 정점 [8] 같이 단일 정점도 위원회 소속 및 대표 가능.

　

① 각 정점별로 최소비용을 모두 구해야하기에

플로이드 와샬 (Floyd Warshall)으로 구현

플로이드 와샬 (Floyd Warshall)

각 정점별 최단거리 비용 테이블 

(도달할 수 없는 경우인  『 INF 』를 『 0 』으로 표현)

 

② dist[][] 테이블에서 위원회의 개수와 연결된 참가자(정점)을 구합니다.

    혼자서도 위원회를 구성할 수 있다.

public static void findCommitteeInfo() {
    boolean[] visited = new boolean[N + 1];
    List<Integer> connectedVertexList = new ArrayList<Integer>();
    
    for (int i = 1; i <= N; i++) {
        if(!visited[i]) {
            cnt++;
            visited[i] = true;
            // 연결된 정점 번호
            connectedVertexList.add(i);
            for (int j = 1; j <= N; j++) {
                // 연결된 정점인 경우 (연결되지 않았거나 자기자신 제외)
                if(dist[i][j] != INF && i != j){
                    // 연결된 정점 번호
                    connectedVertexList.add(j);
                    visited[j] = true;
                }
            }
            // 대표 선출
            leaderList.add(electLeader(connectedVertexList));
            connectedVertexList.clear();
        }
    }
}

 

③ 연결된 정점들 중에서 대표 선정

private static Integer electLeader(List<Integer> connectedVertexList) {
    PriorityQueue<Node> pq = new PriorityQueue<>();

    for(int i=0; i<connectedVertexList.size(); i++) {
        int maxPathCost = Integer.MIN_VALUE;
        int v = connectedVertexList.get(i);
        for(int j=1; j<=N; j++) {
            // 연결된 정점과의 가중치들 중에서 최대 가중치를 구합니다.
            if(dist[v][j] != INF && v != j) {
                maxPathCost = Math.max(maxPathCost, dist[v][j]);
            }
        }
        // 최대 가중치가 가장 작은 정점이 앞에 오도록 우선순위 큐에 넣습니다.
        pq.add(new Node(v, maxPathCost));
    }
    // 대표 정점 반환
    return pq.poll().ID;
}

 

④ 각 위원회의 대표 번호를 작은 수부터 차례로 한 줄에 하나씩 출력한다. (오름차순)

 

대표 선정 기준

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

 Input 

9

8

1 2

2 3

3 4

4 5

4 6

4 7

4 8

4 9

 

 Output 

1

3 

플로이드 와샬(Floyd Warshall) 알고리즘을 이용한 테이블

- 정점 [3]이 대표인 경우, 모든 정점까지의 합 = 14

- 정점 [4]이 대표인 경우, 모든 정점까지의 합 = 11

 

문제에서 요구하는 것은 특정 정점까지의 가중치의 합이 최소가 되는 정점이 아닌

특정 정점까지지의 가중치들 중 최대값이 최소가 되는 정점입니다.

- [Path Cost of x → 3] : 2  1  0  1  2  2  2  2  2 ▶ 『 2 』

- [Path Cost of x → 4] : 3  2  1  0  1  1  1  1  1 ▶ 『 3 』

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    static final int INF = 1000000;
    static int N, M, X, cnt = 0;
    static List<Integer> leaderList;
    static int[][] dist;
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        N = Integer.parseInt(br.readLine()); // 정점의 개수
        M = Integer.parseInt(br.readLine()); // 간선의 개수
        leaderList = new ArrayList<Integer>();
         
        dist = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) continue;
                dist[i][j] = INF;
            }
        }
         
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int cost = 1;
            // 양방향이므로
            dist[u][v] = cost; dist[v][u] = cost; 
        }
 
        // 플로이드 와샬 알고리즘
        floydWarshall();
 
        // 위원회 개수 및 대표 구하기.
        findCommitteeInfo();
         
        // 정답 출력
        System.out.println(cnt);
        Collections.sort(leaderList);
        for(int i=0; i<leaderList.size(); i++) {
            System.out.println(leaderList.get(i));
        }
    }
 
    public static void floydWarshall() {
        // 중간에 거쳐가는 정점 (k)
        for (int k = 1; k <= N; k++) {
            // 출발 정점 (i)
            for (int i = 1; i <= N; i++) {
                // 도착 정점 (j)
                for (int j = 1; j <= N; j++) {
                    // 기존에 저장된 최단 거리와 정점 k를 거쳐가는 (i → k) + (k → j) 경로 중 최소값
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
     
    public static void findCommitteeInfo() {
        boolean[] visited = new boolean[N + 1];
        List<Integer> connectedVertexList = new ArrayList<Integer>();
         
        for (int i = 1; i <= N; i++) {
            if(!visited[i]) {
                cnt++;
                visited[i] = true;
                // 연결된 정점 번호
                connectedVertexList.add(i);
                for (int j = 1; j <= N; j++) {
                    // 연결된 정점인 경우 (연결되지 않았거나 자기자신 제외) 
                    if(dist[i][j] != INF && i != j){
                        // 연결된 정점 번호
                        connectedVertexList.add(j);
                        visited[j] = true;
                    }
                }
                // 대표 선출
                leaderList.add(electLeader(connectedVertexList));
                connectedVertexList.clear();
            }
        }
    }
 
    private static Integer electLeader(List<Integer> connectedVertexList) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
         
        for(int i=0; i<connectedVertexList.size(); i++) {
            int maxPathCost = Integer.MIN_VALUE;
            int v = connectedVertexList.get(i);
            for(int j=1; j<=N; j++) {
                // 연결된 정점과의 가중치들 중에서 최대 가중치를 구합니다.
                if(dist[v][j] != INF && v != j) {
                    maxPathCost = Math.max(maxPathCost, dist[v][j]);
                }
            }
            // 최대 가중치가 가장 작은 정점이 앞에 오도록 우선순위 큐에 넣습니다.
            pq.add(new Node(v, maxPathCost));
        }
        // 대표 정점 반환 
        return pq.poll().ID;
    }
}
 
class Node implements Comparable<Node>{
    int ID, maxPathCost;
     
    Node(int ID, int maxPathCost){
        this.ID = ID;
        this.maxPathCost = maxPathCost;
    }
     
    @Override
    public int compareTo(Node target) {
        return this.maxPathCost - target.maxPathCost; 
    }
}