백준 1939: 중량제한

문제 요약

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

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

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

문제 분류

• 자료 구조
• 그래프 이론
• 그래프 탐색
• 이분 탐색
• BFS
• 최단 경로
• 데이크스트라
• 분리 집합

문제 풀이

정말 다양한 풀이가 있지만, 나는 분리 집합을 이용해서 풀었다.
각 노드를 잇는 간선을 중량 기준 내림차순으로 정렬하여 우선순위 큐에 넣고, 큐에서 하나씩 간선을 추가하며 그래프를 구축한다. 문제에서 주어진 두 정점이 같은 집합이 되면 마지막으로 추가한 간선의 가중치가 정답이 될 것이다.

풀이 코드

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

public class Main {
	static int n, m;
	static int p[];
	
	static int find(int v) {
		if(p[v] == 0) return v;
		p[v] = find(p[v]);
		return p[v];
	}
	
	static void merge(int a, int b) {
		int pa = find(a);
		int pb = find(b);
		if(pa == pb) return;
		p[pb] = pa;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		PriorityQueue<Node> q = new PriorityQueue<>();
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		p = new int[n + 1];
		int a, b, c, res = 0;
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			q.offer(new Node(c, a, b));
		}
		st = new StringTokenizer(br.readLine());
		a = Integer.parseInt(st.nextToken());
		b = Integer.parseInt(st.nextToken());
		while(find(a) != find(b)) {
			Node node = q.poll();
			res = node.w;
			merge(node.a, node.b);
		}
		System.out.println(res);
	}
}

class Node implements Comparable<Node> {
	int w;
	int a;
	int b;
	public Node(int w, int a, int b) {
		this.w = w;
		this.a = a;
		this.b = b;
	}
	
	@Override
	public int compareTo(Node o) {
		return Integer.compare(o.w, this.w);
	}
}