[백준] 1939번. 중량제한(JAVA)

문제

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

---

풀이(20분)

import java.io.*;
import java.util.*;

public class Main {

    static int[] parent;

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

        st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); // 도시의 개수
        int m = Integer.parseInt(st.nextToken()); // 도로의 개수

        parent = new int[n+1];
        for(int i = 0; i < n+1; i++){
            parent[i] = i; // 최초 부모를 자기 자신으로 초기화
        }

        List<Edge> edges = new ArrayList<>();

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            if(first > second){ // 앞에 작은 값이 오게
                int temp = first;
                first = second;
                second = temp;
            }
            edges.add(new Edge(first, second, weight));
        }

        Collections.sort(edges); // 비용 기준 내림차순 정렬

        int max = 0;
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        int idx = 0;
        while(find(start) != find(end)){ // 부모가 같을때까지
            Edge edge = edges.get(idx);
            union(edge.first, edge.second); // 유니온
            max = edge.weight; // 최댓값 수정
            idx++;
        }

        System.out.println(max);
    }

    public static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) { // 이미 같은 집합이 아닐 때만 병합
            if (rootA < rootB) { // 인덱스가 작은 것을 우선으로
                parent[rootB] = rootA;
            } else {
                parent[rootA] = rootB;
            }
        }
    }

    // Find 연산 (경로 압축 포함)
    public static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 경로 압축
        }
        return parent[x];
    }

    static class Edge implements Comparable<Edge>{
        int first, second, weight;

        public Edge(int first, int second, int weight) {
            this.first = first;
            this.second = second;
            this.weight = weight;
        }

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

---

문제 풀이 전략

 

가장 중요한 알고리즘은 union-find 알고리즘이다.

[도구정리] Union-Find 알고리즘

또한, 단순 union-find 알고리즘을 적용하는 것이 아닌 꼭 경로 압축된 버전으로 문제를 해결해야 한다.

이 문제의 경우 부모를 찾는 일이 많기 때문에 경로 압축을 통해 한번 탐색된 부모에 대해서는 많은 연산을 진행하지 않게 해주어야 한다는 것이다.

 

풀이를 보고 의문이 들 수 있는 부분은 아마 1->2 경로를 하나만 확인하면 되는데 왜 1->2라는 경로가 가중치만 큰 편에 속한다면 나오는 족족 계산하는 것일까? 일 것이다.

 

- 1. 동일한 경로에 대해 최댓값만 확인하는 것은 물론 좋은 방식이다.

- 2. 동일한 경로라는 것을 파악하려면 10000x10000 배열을 유지해야 한다. -> 이는 메모리 낭비가 말도 안 된다.

- 3. 어차피 1->2를 5로 잡든 1->2를 10으로 잡든 결국은 1->3이 완성되기 전까지는 별 의미가 없다.

-> 3번이 중요하다. 어차피 부모가 똑같아지지 않는다면 내림차순으로 정렬된 경로들의 리스트에서 어떤 경로를 10으로 보나 5로 보나 상관이 없다는 것이다. 왜냐하면 부모가 같아질 때는 결국 3이 될 수도 있으니까!