백준 13905 - 세부

문제

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

리뷰

크루스칼을 이용해 풀이할 수 있는 문제였다.

주어진 간선들의 정보를 비용 기준 최대힙에 저장한다. 크루스칼 로직에선 MST를 구성할 때
이 힙을 이용하여 비용이 큰 간선부터 채택한다. 그리고 $s$와 $e$간의 경로가 형성될 경우
(find(s)==find(e)) 해당 시점에 채택한 간선을 반환해주면 경로상의 간선중 비용이
가장 작은, 즉 가능한 빼빼로의 최대 개수를 도출할 수 있다.

로직의 시간복잡도는 크루스칼의 $O(Ma(N))$으로 수렴하고 이는 $N=100,000$, $M=300,000$인
최악의 경우에도 무난히 제한 조건 1초를 통과한다.

코드

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

import static java.lang.Integer.*;

public class Main {
    static int[] parent;
    static PriorityQueue<Edge> pq = new PriorityQueue<>((e1, e2) -> Integer.compare(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());
        int N = parseInt(st.nextToken());
        int M = parseInt(st.nextToken());

        parent = new int[N + 1];
        Arrays.fill(parent, -1);

        st = new StringTokenizer(br.readLine());
        int s = parseInt(st.nextToken());
        int e = parseInt(st.nextToken());

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

            pq.offer(new Edge(u, v, w));
        }

        int result = kruskal(s, e);
        System.out.println(result == -1 ? "0" : result);
        br.close();
    }

    static int kruskal(int s, int e) {
        int r1, r2;

        while (!pq.isEmpty()) {

            Edge edge = pq.poll();
            r1 = find(edge.u);
            r2 = find(edge.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;
            }

            if (find(s) == find(e))
                return edge.w;
        }

        return -1;
    }

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

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

    static class Edge {
        int u, v, w;

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

결과