[백준] 1939. 중량 제한

문제 링크

1. 문제 설명

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

• 입력
  첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

• 출력
  첫째 줄에 답을 출력한다.

2. 문제 접근

크게 두 가지 풀이 방법이 있습니다.

1. 최대 중량을 이분 탐색으로 찾으며 BFS 또는 DFS로 그래프 탐색을 진행합니다. 이 경우에는 탐색 대상인 중량보다 중량 제한이 큰 다리만 통과 가능하다고 하여 목표 지점 A에서 B를 갈 수 있는지 판단해야 합니다.

2. 중량 제한이 가장 큰 간선부터 유니온-파인드 알고리즘을 이용해 연결하며 간선의 두 섬을 유니온 합니다. 어느 지점이 되면 A와 B가 같은 집합에 속하게 되면 A에서 B를 갈 수 있다고 판단하고 사용한 다리 중 최저 중량 제한을 찾습니다.

저는 2번 방법으로 풀었습니다. 유니온 파인드 풀이의 시간복잡도가 최대 $O(M)$인데 이분 탐색의 경우 $O(logC*N)$이고 BFS의 메모리 부담 문제도 있어서 그런지 실행 속도가 빠른 코드들은 대부분 이 풀이를 사용하고 있었습니다. 일종의 역 크루스칼 같은 풀이라고 생각합니다.

3. 문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static StringTokenizer st;
	static int n;
	static int[] parent;
	
	static class Edge implements Comparable<Edge>{
		int from;
		int to;
		int weight;
		public Edge(int from, int to, int weight) {
			this.from = from;
			this.to = to;
			this.weight = weight;
		}
		@Override
		public int compareTo(Edge o) {
			return o.weight - weight;
		}
		
	}
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) parent[i] = i;
        
        Queue<Edge> queue = new PriorityQueue<>();
        while (m --> 0) {
        	st = new StringTokenizer(br.readLine());
        	int from = Integer.parseInt(st.nextToken());
        	int to = Integer.parseInt(st.nextToken());
        	int weight = Integer.parseInt(st.nextToken());
        	queue.add(new Edge(from, to, weight));
        }
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int ans = 0;
        while (!isUnion(a,b)) {
        	Edge cur = queue.poll();
        	int from = cur.from;
        	int to = cur.to;
        	int weight = cur.weight;
        	union(from, to);
        	ans = weight;
        }
        System.out.println(ans);
    	
    }
    
    static boolean isUnion(int a, int b) {
    	if (find(a) == find(b)) return true;
    	return false;
    }
    
    static void union(int a, int b) {
    	a = find(a);
    	b = find(b);
    	if (a != b) parent[a] = b;
    }
    
    static int find(int a) {
    	if (parent[a] != a) return (parent[a] = find(parent[a]));
    	return a;
    }
    
}