백준 11085 : 군사 이동

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

11085번: 군사 이동

[ 문제풀이 ]

크루스칼 알고리즘을 활용해서 c, v가 연결될 때까지 가장 넓은 길부터 차례대로 연결해주면 되는 문제이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	static class Edge implements Comparable<Edge> {
		int from, to, width;
		
		Edge (int from, int to, int width) {
			this.from = from;
			this.to = to;
			this.width = width;
		}

		@Override
		public int compareTo(Edge o) {
			return o.width - this.width;
		}
	}
	
	static int p, w, c, v;
	static int[] parent;
	static PriorityQueue<Edge> pq;
	
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			p = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());
			
			st = new StringTokenizer(br.readLine());
			c = Integer.parseInt(st.nextToken());
			v = Integer.parseInt(st.nextToken());
			
			parent = new int[p];
			for (int i = 0; i < p; ++i) parent[i] = i;
			
			pq = new PriorityQueue<>();
			for (int i = 0; i < w; ++i) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				int width = Integer.parseInt(st.nextToken());
				pq.offer(new Edge(from, to, width));
			}
			
			while (!pq.isEmpty()) {
				Edge e = pq.poll();
				
				union(e.from, e.to);
				if (isSameParent(c, v)) {
					bw.write(e.width + "\n");
					break;
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static int getParent(int v) {
		return v == parent[v] ? v : (parent[v] = getParent(parent[v]));
	}
	
	public static void union(int a, int b) {
		a = getParent(a);
		b = getParent(b);
		parent[b] = a;
	}
	
	public static boolean isSameParent(int a, int b) {
		return getParent(a) == getParent(b);
	}
}