[알고리즘] 백준 > #11085. 군사 이동

풀고보니 쉬운데 풀이방법을 꽤 길게 고민했던 문제다!

문제링크

백준 #11085. 군사 이동

풀이방법

큰틀은 그리디와 유니온파인드이다!

그리디 방식으로 가장 큰 너비의 다리를 순차적으로 가져와 그 사이를 이어준다.(다리 너비 값을 내림차순으로 우선순위를 갖는 우선순위큐를 사용) 다리를 둘 때마다 c와 v가 같은 그룹에 속하는지 확인한다! 이어주고 같은 그룹에 속하는지 확인하는게 union, find 연산이므로 Disjoint-set 자료구조를 사용한다.

고민한거에 비해 설명도 굉장히 짧은 문제네요;

코드

import java.util.*;
public class BOJ11085 {

    static PriorityQueue<Bridge> bridges = new PriorityQueue<>();
    static int[] parent;

    static final int ROOT = -1;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int p = sc.nextInt();
        int w = sc.nextInt();

        int c = sc.nextInt();
        int v = sc.nextInt();

        while (--w >= 0) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int width = sc.nextInt();

            bridges.offer(new Bridge(a, b, width));
        }

        parent = new int[p];
        for (int i = 0; i < p; i++) parent[i] = ROOT;

        int lastWidth = 1001;
        while (!bridges.isEmpty()) {
            Bridge head = bridges.poll();
            lastWidth = head.width;

            merge(head.nodeA, head.nodeB);
            if (!((parent[c] == ROOT) && (parent[v] == ROOT)) && (find(c) == find(v))) break;
        }

        System.out.print(lastWidth);
    }

    private static int find(int id) {
        if (parent[id] == ROOT) return id;
        else {
            parent[id] = find(parent[id]);
            return parent[id];
        }
    }

    private static void merge(int a, int b) {
        int aParent= find(a);
        int bParent = find(b);

        if (aParent != bParent) parent[bParent] = a;
    }
}

class Bridge implements Comparable<Bridge> {

    public int nodeA;
    public int nodeB;
    public int width;

    public Bridge(int nodeA, int nodeB, int width) {
        this.nodeA = nodeA;
        this.nodeB = nodeB;
        this.width = width;
    }

    @Override
    public int compareTo(Bridge o) {
        return o.width - this.width;
    }
}