백준 23034 (조별과제 멈춰!) - java

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

23034번: 조별과제 멈춰!

 

문제

교수님이 시험 기간에 조별 과제를 준비하셨다...! 가톨릭대학교의 조교 아리는 N명의 학생을 2개의 조로 구성하여 과제 공지를 하려 한다. 이때, 구성된 각 조의 인원은 1명 이상이어야 한다. 각 학생은 1~N의 정수 중 고유한 번호를 학번으로 갖는다.

모든 것이 귀찮은 아리는 각 조의 팀장에게만 공지를 전달한다. 아리는 N명의 학생 사이에 있는 총 M개의 회선의 리스트를 가지고 있다. 리스트에는 각 회선에 연결된 두 학생의 학번 A와 B, 연락에 필요한 비용 C가 적혀있다. 회선이 연결된 두 학생은 서로 연락이 가능하다. 아리가 각 팀장에게 공지를 전달하면, 각 팀장과 공지를 알게 된 팀원은 같은 조의 모든 팀원에게 공지 내용을 회선을 통해서만 전달한다. 어떤 학생이 팀장이 되어도 모든 학생은 공지 내용을 전달받을 수 있다.

아리는 공지 채팅방을 만들 생각은 안 하고, 모든 학생이 공지 내용을 알게 될 때까지 학생들이 연락하며 소요되는 비용의 총합 T의 최솟값을 알고 싶어졌다. 그것을 구하여 팀장을 정한 뒤 조를 구성하려고 한다.

아리는 다음과 같은 Q개의 질문을 한다.

• X Y : X와 Y가 팀장일 때, T의 최솟값은 무엇인가?

Q개의 질문에 답할 수 있는 프로그램을 작성하시오.

 

유형 : MST + 그래프 탐색

 

접근 방식

• 문제를 이해하는 과정에서 조금의 노력이 필요하다.
• '어떤 학생이 팀장이 되어도 모든 학생은 공지 내용을 전달받을 수 있다.' 라는 말이 의미하는 것은 어느 지점에서라도 다른 지점으로의 경로가 존재하고 해당 값들이 최소여야 하는 것이다. 즉 MST다.
  • MST를 만들면서 해당 간선들로 그래프를 만든다.
  • 두 지점이 팀장이 된다면 어떤 변화가 발생할까?
    • 답은 간단하다. 해당 두 지점 간의 경로에 있어 가장 길이가 긴(최장 경로)의 값이 빠진다.
    • 즉 MST로 만들어진 그래프에서 DP[i][j]를 통해 i지점에서 j지점으로 갈 때 최장 길이의 간선 값을 저장한다.

전체 코드

import java.util.*;
import java.io.*;
public class Main {
    static int n = 0;
    static int m = 0;

    static ArrayList<Node>[] graph;
    static int[] root;

    static int[][] dp;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        root = new int[n+1];
        graph = new ArrayList[n+1];
        dp = new int[n+1][n+1];

        for(int i=1;i<=n;i++){
            root[i] = i;
            graph[i] = new ArrayList<>();
        }

        PriorityQueue<Point> pq = new PriorityQueue<>(
                (x,y) -> x.c - y.c
        );

        for(int i=1;i<=m;i++){
            st = new StringTokenizer(bf.readLine(), " ");

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            pq.add(new Point(v1,v2,c));
        }

        int count = 0;
        int total = 0;

        // MST 생성
        while(!pq.isEmpty()){
            Point cur = pq.poll();
            
            // Union - Find
            if(find(cur.v1) != find(cur.v2)){
                union(cur.v1,cur.v2);
                total += cur.c; // 총량 계산
                count += 1;

                graph[cur.v1].add(new Node(cur.v2,cur.c));
                graph[cur.v2].add(new Node(cur.v1,cur.c)); // 선택된 간선으로 그래프 구성
            }

            if(count == n-1) // MST는 n-1개의 간선을 가진다.
                break;
        }

        for(int i=1;i<=n;i++){
            bfs(i); // BFS로 각 정점으로부터 모든 정점까지 거리 중 최장 간선 값을 DP 테이블에 저장
        }

        st = new StringTokenizer(bf.readLine(), " ");
        int k = Integer.parseInt(st.nextToken());

        for(int i=1;i<=k;i++){
            st = new StringTokenizer(bf.readLine(), " ");
            int x1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());

            sb.append(total - dp[x1][x2]); // 계산
            sb.append("\n");
        }

        System.out.print(sb);
        bf.close();
    }
    static void bfs(int s){
        Queue<Node> q = new LinkedList<>();
        boolean[] v = new boolean[n+1];

        q.add(new Node(s,0));
        v[s] = true;

        while(!q.isEmpty()){
            Node cur = q.poll();

            for(Node next : graph[cur.v]){

                if(!v[next.v]){
                    v[next.v] = true;
                    dp[s][next.v] = Math.max(cur.c,next.c); // 출발지점으로부터 도착지점까지 최장 거리 간선 갱신
                    q.add(new Node(next.v,dp[s][next.v]));
                }
            }
        }
    }

    static int find(int x){
        if(x == root[x])
            return root[x];

        return root[x] = find(root[x]);
    }

    static void union(int x,int y){
        x = find(x);
        y = find(y);

        if(x < y)
            root[y] = x;
        else
            root[x] = y;
    }
}
class Point{
    int v1;
    int v2;
    int c;

    Point(int v1,int v2,int c){
        this.v1 = v1;
        this.v2 = v2;
        this.c = c;
    }
}
class Node{
    int v;
    int c;

    Node(int v,int c){
        this.v = v;
        this.c = c;
    }
}