백준 11085 - 군사 이동

문제

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

리뷰

유니온 파인드를 이용해 풀이할 수 있는 간단한 문제였다.

우선 간선(길)을 표현하기 위해 Edge 클래스를 정의하였다. 입력을 받으며 Edge를 형성하여
비용 기준 최대힙에 저장한다. 이후 유니온 파인드를 이용하여 간선을 하나씩 채택하며
$c$와 $v$ 간 경로가 설정될 때까지 수행하며, 채택한 경로상에서 가장 작은 간선의 너비를
cost에 갱신해주어 답을 구하였다. 너비가 넓은 간선부터 최대힙에서 꺼내어 유니온 연산을
수행하고 $c$와 $v$간 경로가 설정되자마자 루프를 빠져나오기 때문에, 최종적으로 cost 에는
가장 좁은 길의 너비의 최대값이 저장될 수 있게 된다.

로직의 시간복잡도는 $O(wa(p))$ 꼴로 수렴하고 $w=50,000$, $p=1,000$인 최악의 경우에도
시간 제한 조건 2초를 무난히 통과한다.

코드

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.MAX_VALUE;
import static java.lang.Integer.parseInt;

public class Main {
    static int cost = MAX_VALUE;
    static int[] parent;
    static PriorityQueue<Edge> pq = 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());
        int p = parseInt(st.nextToken());
        int w = parseInt(st.nextToken());

        parent = new int[p];
        st = new StringTokenizer(br.readLine());
        int c = parseInt(st.nextToken());
        int v = parseInt(st.nextToken());

        int a, b, tempW;
        while (w-- > 0) {
            st = new StringTokenizer(br.readLine());
            a = parseInt(st.nextToken());
            b = parseInt(st.nextToken());
            tempW = parseInt(st.nextToken());

            pq.offer(new Edge(a, b, tempW));
        }

        int r1, r2;
        Arrays.fill(parent, -1);

        while (!pq.isEmpty()) {
            if (find(c) == find(v)) break;

            Edge e = pq.poll();

            r1 = find(e.u);
            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;
            }

            cost = Math.min(cost, e.w);
        }

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

    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;
        }
    }
}

결과