[백준 1939] 중량제한, 크루스칼 풀이

🔗 문제링크 🔗

1939번: 중량제한

---

🌟 생각 흐름 🌟

기존의 크루스칼 문제에서는 최단 경로를 계산하기 위해서 최단 경로를 기준으로 정렬을 하였다

하지만 해당 문제에서는 다리를 건널 때 가장 많이 적재할 수 있는 양을 물어보는 것이므로 가장 높은 값을 기준으로 정렬한다(내림차순)

만약 시작 지점과 끝지점이 한사이클안에 있다고 판단되는 순간 현재 적재량을 싫고 나를 수 있다는 소리이므로 멈추고 리턴한다. 

 

-- 이진탐색을 이용한 풀이법은 이후에 추가하겠습니다

---

🍳 코드 🍳

 

package 백준.graph.mst.kruskal;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class boj_1939_중량제한 {
    private static final ArrayList<Bridge> bridges = new ArrayList<>();
    private static int[] parents;

    private static class Bridge implements Comparable<Bridge> {
        int start;
        int end;
        int weight;

        public Bridge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int bridgeCnt = Integer.parseInt(st.nextToken());
        int line = Integer.parseInt(st.nextToken());


        while (line-- > 0) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1;
            int end = Integer.parseInt(st.nextToken()) - 1;
            int weight = Integer.parseInt(st.nextToken());

            bridges.add(new Bridge(start, end, weight));
        }
        st = new StringTokenizer(br.readLine());

        parents = new int[bridgeCnt];
        for (int i = 0; i < bridgeCnt; i++) {
            parents[i] = i;
        }
        System.out.println(findMaxWeight(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1));
    }

    private static int findMaxWeight(int start, int end) {
        Collections.sort(bridges);
        for (Bridge bridge : bridges) {

            unionParents(bridge.start, bridge.end);

            // 한 사이클 안에 있다, 갈 수 있다.
            if (findParent(start) == findParent(end)) {
                return bridge.weight;
            }
        }
        return 0;
    }

    private static void unionParents(int a, int b) {
        a = findParent(a);
        b = findParent(b);

        if (a != b) {
            if (a < b) parents[b] = a;
            else parents[a] = b;
        }
    }

    private static int findParent(int a) {
        if (parents[a] == a) return a;
        return parents[a] = findParent(parents[a]);
    }

}