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

백준 13418 학교 탐방하기 GoldIII - JAVA 📌

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

문제 설명

문제 풀이

---

접근 💡

0번에서 시작하는 최소신장트리를 구하는 문제이다.

0은 오르막길, 1은 내리막길이고 오르막길인 간선에서만 비용이 1 증가한다.

 

문제에서는 최악의 비용이 발생하는 경우와 최선의 비용이 발생하는 경우의 비용 차를 요구한다.

 

최소신장트리 알고리즘인 프림 알고리즘과 크루스칼 알고리즘을 사용하여 풀 수 있다.

두 알고리즘 모두 그리디 알고리즘에 기반한 알고리즘이기 때문에, 0을 우선순위로 두는 정렬, 1을 우선순위로 두는 정렬을 하여 최대비용과 최소 비용을 구해보자

 

 

코드 💡

1. 크루스칼 풀이

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

public class Main {

    static int[][] graph;
    static int[] p;
    static int N;
    static int M;
    static int ans;

    public static void main(String[] args) 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());

        graph = new int[M + 1][3];
        for (int i = 0; i < M + 1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //최소 구하기. 최소를 구하려면 내리막(1)이 우선적으로 와야함
        Arrays.sort(graph, (o1, o2) -> o2[2] - o1[2]);
        makeSet();
        int min = kruskal();

        //최대 구하기. 최대를 구하려면 오르막(0)이 우선적으로 와야함
        Arrays.sort(graph, ((o1, o2) -> o1[2] - o2[2]));
        makeSet();
        int max = kruskal();

        ans = max - min;
        System.out.println(ans);

    }

    private static void makeSet() {
        p = new int[N + 1];
        for (int i = 0; i < N + 1; i++) {
            p[i] = i;
        }
    }

    private static int find(int x) {
        if (p[x] == x) {
            return x;
        }
        return p[x] = find(p[x]);
    }

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

        if (rootX == rootY) {
            return;
        }

        if (rootX < rootY) {
            p[rootY] = rootX;
        }else {
            p[rootX] = rootY;
        }
    }

    private static int kruskal() {
        int res = 0;

        for (int i = 0; i < graph.length; i++) {
            if (find(graph[i][0]) != find(graph[i][1])) {
                if (graph[i][2] == 0) {
                    res++;
                }
                union(find(graph[i][0]), find(graph[i][1]));
            }
        }

        return res * res;
    }
}

 

 2. 프림 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static class Edge {
        int w;
        int cost;

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

        @Override
        public String toString() {
            return "Edge{" +
                    "w=" + w +
                    ", cost=" + cost +
                    '}';
        }
    }

    static int N;
    static int M;
    static List<Edge>[] graph;

    public static void main(String[] args) 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());

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

        for (int i = 0; i < M + 1; i++) {
            st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph[v].add(new Edge(w, cost));
            graph[w].add(new Edge(v, cost));
        }


        int min = minPrim(0);
        //System.out.println(min);
        //System.out.println(Arrays.deepToString(graph));

        int max = maxPrim(0);
        //System.out.println(max);

        System.out.println(max - min);
    }

    private static int minPrim(int start) {

        //최소를 구하려면 1이 먼저 와야함, 1부터 우선순위를 갖는 큐 만들기
        PriorityQueue<Edge> pq = new PriorityQueue<>((o1, o2) -> o2.cost - o1.cost);
        boolean[] visit = new boolean[N + 1];
        pq.offer(new Edge(start, 1));

        int res = 0;
        while (!pq.isEmpty()) {
            //System.out.println(pq);
            Edge edge = pq.poll();
            int vertex = edge.w;
            int cost = edge.cost;

            if (visit[vertex]) continue;

            visit[vertex] = true;
            if (cost == 0) {
                res++;
            }

            for (Edge e : graph[vertex]) {
                if (!visit[e.w]) {
                    pq.offer(e);
                }
            }
        }

        return res * res;
    }

    private static int maxPrim(int start) {

        //최소를 구하려면 1이 먼저 와야함, 1부터 우선순위를 갖는 큐 만들기
        PriorityQueue<Edge> pq = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        boolean[] visit = new boolean[N + 1];
        pq.offer(new Edge(start, 1));

        int res = 0;
        while (!pq.isEmpty()) {
            //System.out.println(pq);
            Edge edge = pq.poll();
            int vertex = edge.w;
            int cost = edge.cost;

            if (visit[vertex]) continue;

            visit[vertex] = true;
            if (cost == 0) {
                res++;
            }

            for (Edge e : graph[vertex]) {
                if (!visit[e.w]) {
                    pq.offer(e);
                }
            }
        }

        return res * res;
    }
}