백준 13418 - 학교 탐방하기

문제

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

리뷰

• 오르막길을 가장 많이 선택하는 경우
• 오르막길을 가장 적게 선택하는 경우

위 두 가지 경우로 나누어 MST를 형성하는 과정에서 오르막길의 개수를 카운팅하여
그 제곱의 차이를 도출하면 되는 문제였다.

비용이 가장 많이 드는 경우는 엄연히 MST라고 말할 순 없지만 편의상 그렇게 적었다.

각각의 경우에 맞게 간선을 선택하기 위해 간선의 비용에 따른 최대힙, 최소힙을
설정하고 입력으로 간선을 받을 때 두 힙에 모두 삽입한 후 각 힙에 대해 크루스칼을
실행하였다. 크루스칼의 실행 과정에서 오르막길의 개수(uphillCount)를 구하여
반환하도록 로직을 구성하였다.

문제 풀이시 유의할 점은 오르막길이 0으로 표현되고 내리막길이 1로 표현된다는
점이었다. 필자는 그냥 0과 1 입력을 확인한 후 값을 반대로 저장해주었다.

로직의 시간복잡도는 크루스칼의 복잡도인 $O(ElogE)$로 수렴하고, 이는 $E$가
최악의 경우인 $E=N(N-1)/2=1000\times 999/2$ 일 때도 무난히 제한 조건인
1초를 통과한다.

코드

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

import static java.lang.Integer.*;

public class Main {
    static int N;
    static int[] parent;
    static PriorityQueue<Edge> minHeap=new PriorityQueue<>(Comparator.comparingInt(edge->edge.w));
    static PriorityQueue<Edge> maxHeap=new PriorityQueue<>((e1, e2)->e2.w-e1.w);

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        N= parseInt(st.nextToken());
        int M=parseInt(st.nextToken())+1;

        parent=new int[N+1];

        int u, v, w;
        while(M-->0){
            st=new StringTokenizer(br.readLine());
            u=parseInt(st.nextToken());
            v=parseInt(st.nextToken());
            w=parseInt(st.nextToken())==0?1:0;

            Edge e = new Edge(u, v, w);
            minHeap.offer(e);
            maxHeap.offer(e);
        }

        System.out.println(solution());
        br.close();
    }

    static int find(int u){
        if(parent[u]<0) return u;

        return parent[u]=find(parent[u]);
    }

    static int kruskal(PriorityQueue<Edge> heap){
        Arrays.fill(parent, -1);
        int edgeCount=0;
        int uphillCount=0;

        while(edgeCount<N){
            Edge e = heap.poll();
            int r1 = find(e.u);
            int r2 = find(e.v);

            if(r1==r2) continue;

            if(parent[r1]<parent[r2]){
                parent[r1]+=parent[r2];
                parent[r2]=r1;
            }else{
                parent[r2]+=parent[r1];
                parent[r1]=r2;
            }

            edgeCount++;
            if(e.w==1)
                uphillCount++;
        }

        return uphillCount;
    }

    static int solution(){
        int maxCost = kruskal(maxHeap);
        maxCost*=maxCost;

        int minCost = kruskal(minHeap);
        minCost*=minCost;

        return maxCost-minCost;
    }

    static class Edge{
        int u, v, w;

        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }
}

결과