[백준] 13418 학교 탐방하기 (JAVA)

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

13418번: 학교 탐방하기

---

 

최소 신장 트리 (MST)를 알아야 풀 수 있는 문제다.

문제는 (최대 신장 트리 - 최소 신장 트리)의 값을 요구한다.

제곱을 해줘야 하긴 하지만 사소하기 때문에

MST를 적용하면 풀 수 있는 문제다.

 

크루스칼, 프림 모두 적용 가능하며 크루스칼을 이용해서 해결했다.

 

우선순위 큐에서 최대 신장 트리, 최소 신장 트리로 정렬할 수 있도록

두 가지 방식으로 정렬하는 큐를 만들어서 

간선들을 넣어준후 크루스칼 알고리즘을 적용했다.

 

이 문제의 최대 주의할 점은

오르막길이 1이라고 착각할 수 있다.

오르막길은 0이다.

예제는 오르막길이 1이라고 판단해도 정답이 되기 때문에 주의해야 한다.

 

---

코드구현

 

import java.io.*;
import java.util.*;
 
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    static Queue<Edge> q1;
    static Queue<Edge> q2;
    static int[] arr;
 
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int E = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken()) + 1;
 
        arr = new int[E+1];
        for(int i = 0; i<arr.length; i++){
            arr[i] = i;
        }
        q1 = new PriorityQueue<>((o1, o2) -> o1.v - o2.v);
        q2 = new PriorityQueue<>((o1, o2) -> o2.v - o1.v);
 
        while(V-- > 0){
            st = new StringTokenizer(br.readLine());
            int w1 = Integer.parseInt(st.nextToken());
            int w2 = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
 
            Edge e = new Edge(w1,w2,v);
            q1.offer(e);
            q2.offer(e);
        }
 
        //
 
        int ms = (int) Math.pow(mst(0,q1),2); // max
 
        //
 
        for(int i = 0; i<arr.length; i++)
            arr[i] = i;
        int Ms = (int) Math.pow(mst(0,q2), 2); // min
        System.out.println(ms-Ms);
 
    }
    public static int find(int e){ // 대표원소 갖고오기.
        if(arr[e] == e)
            return e;
        else
            return arr[e] = find(arr[e]);
    }
 
    public static void union(int w1, int w2){ // 대표원소 바꿔주기.
        w1 = find(w1);
        w2 = find(w2); // 대표원소를 찾아왔음
        if(w1 < w2){
            arr[w2] = w1;
        }else
            arr[w1] = w2;
    }
 
    public static int mst(int start, Queue<Edge> q){
        int sum = 0;
        while(!q.isEmpty()){
            Edge e = q.poll();
            int w11 = e.w1;
            int w21 = e.w2;
            int v1 = e.v;
 
            if(find(w11) != find(w21)){
                union(w11, w21);
                // 처리부분.
                if(v1 == 0)
                    sum += 1;
            }
        }
        return sum;
    }
}
 
class Edge {
    int w1;
    int w2;
    int v;
    Edge(int w1, int w2, int v){
        this.w1 = w1;
        this.w2 = w2;
        this.v = v;
    }
}
 
 
 
 

 

 

 

 

 

---