[BOJ] 27498 : 연애 혁명(Java)

문제 링크

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

27498번: 연애 혁명

---

💡 풀이

문제에서 주어진 입력값이 학생1, 학생2, 애정도, 성사 여부 입니다. 즉, 노드1과 노드2가 주어지고 이 간선의 가중치가 주어진 것으로 해석할 수 있습니다. 또한, 문제 조건에서  "포기하도록 만들 수 있는 경우가 여러가지일 경우 포기하도록 만든 애정도의 합을 최소화한다." 라고 했기에 최소 신장 트리(MST)를 떠올릴 수 있습니다. 

 

하지만, 여기서 주의해야 할 점이 있습니다. 

구하고자 하는 정답은 "포기하도록 만든 애정도의 합의 최솟값" 입니다. 즉, 주어진 간선들로 트리(MST)를 만들었을 때, 이에 포함되지 못한 간선들의 합을 구하는 것입니다.

이때, 이 포함되지 못한 간선들의 합이 최소가 되기 위해서는 트리의 간선들의 가중치 합이 최대가 되어야 합니다. 

$$ 전체 가중치 - 트리 간선들의 가중치 = 포함되지 못한 간선들의 합 $$

이 되기 때문입니다. 

그래서 트리들의 가중치의 합이 최대가 되도록 만들어야 합니다.

엄밀히 말하면 "최소" 신장 트리는 아니게 됩니다. 하지만, 구현 방식은 같기 때문에 알고리즘을 사용할 수 있습니다. 

Edge 클래스

간선들의 정보를 저장하는 Edge 클래스를 선언합니다. 이때, 우선순위 큐에 들어가는 순서는 가중치가 큰 순서, 즉 내림차순으로 들어가야 하기 때문에, compareTo 메서드를 구현하는 과정에서 이를 처리해줍니다.

static class Edge implements Comparable<Edge> {
    int student1;
    int student2;
    int weight;

    public Edge(int student1, int student2, int weight) {
        this.student1 = student1;
        this.student2 = student2;
        this.weight = weight;
    }


    @Override
    public int compareTo(Edge o) {
        return o.weight - this.weight;
    }
}

 

또, 성사 여부가 1 인 간선들은 무조건 트리의 간선으로 구성이 되기 때문에, 입력값을 받는 과정에서 무조건 포함시켜 줍니다. 이때 이미 포함된 간선으로 처리되기 때문에 우선순위 큐에 넣어줄 필요가 없습니다. 

static void prevUnion(int n1, int n2, int weight, int check) {
    if(check == 1){
        union(n1, n2);
        answer += weight;
        return;
    }
    pq.add(new Edge(n1, n2, weight));
}

 

전체 코드

전체적인 코드는 다음과 같습니다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Q27498 {
    static int[] parents;
    static int N, M, answer, affections;
    static PriorityQueue<Edge> pq = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        initInput();
        makeMst();

        System.out.println(affections - answer);
    }

    static void initParents() {
        parents = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            parents[i] = i;
        }
    }

    static void initInput() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        answer = 0;
        affections = 0; // 전체 애정도(가중치)의 합

        initParents();

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int student1 = Integer.parseInt(st.nextToken());
            int student2 = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            int isLove = Integer.parseInt(st.nextToken());

            affections += weight;

            prevUnion(student1, student2, weight, isLove);
        }
    }

    static void makeMst() {
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();

            if (!isSameParent(find(edge.student1), find(edge.student2))) {
                answer += edge.weight;
                union(edge.student1, edge.student2);
            }
        }
    }

    static void union(int n1, int n2) {
        n1 = find(n1);
        n2 = find(n2);

        if(n1 != n2)
            parents[n2] = n1;
    }

    static int find(int node) {
        if(parents[node] == node)
            return node;

        return parents[node] = find(parents[node]);
    }

    static void prevUnion(int n1, int n2, int weight, int check) {
        // 성사 여부가 1인 경우, 무조건 트리에 포함시켜야 한다. 
        if(check == 1){
            union(n1, n2);
            answer += weight;
            return;
        }
        pq.add(new Edge(n1, n2, weight));
    }

    static boolean isSameParent(int n1, int n2) {
        return find(n1) == find(n2);
    }

    static class Edge implements Comparable<Edge> {
        int student1;
        int student2;
        int weight;

        public Edge(int student1, int student2, int weight) {
            this.student1 = student1;
            this.student2 = student2;
            this.weight = weight;
        }


        @Override
        public int compareTo(Edge o) {
            return o.weight - this.weight;
        }
    }
}