백준 | 13905번. 세부 - 최소 스패닝 트리 문풀

⬛ 백준 13905번. 세부 - 최소 스패닝 트리 문풀

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

13905번: 세부

문제

빼빼로 데이를 맞아 혜빈이와 숭이는 세부에 있는 섬에 놀러 갔다. 섬은 바다 위에 떠다니는 집과 집들을 연결하는 오크나무로 되어있는 다리로 이뤄져 있다. 숭이는 혜빈이에게 깜짝 이벤트를 해주기 위해 섬 관리자에게 혜빈이를 이벤트장소에 머물게 해달라고 하였다. 이벤트 당일 날 숭이는 금으로 된 빼빼로들을 들고 이벤트 장소로 이동하려 했다. 하지만 아뿔싸! 각 다리마다 다리 위를 지날 수 있는 무게 제한이 존재했다. 비싼 금빼빼로를 가면서 버리기 아깝던 숭이는 자신이 머물던 집에서 자신이 혜빈이에게 갈 수 있는 최대한의 금빼빼로만을 들고 가려고 한다. 따라서 숭이는 인공위성조차 해킹할 수 있는 당신에게 혜빈이에게 들고 갈 수 있는 최대한의 금빼빼로 개수를 알려달라고 부탁했다. 당신은 인공위성을 해킹하여 집들의 번호와 다리의 무게제한을 알아내었다. 이 정보를 가지고 빨리 숭이를 도와주자.

힌트 그림

(금빼빼로 하나의 무게는 1이고, 숭이의 몸무게는 고려하지 않는다.)

입력

첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄에는 다리의 정보가 주어진다. 각 줄은 “집의 번호 h1(1≤h1≤N), 집의 번호 h2(1≤h2≤N), 다리의 무게제한 k(1≤k≤1,000,000)” 형식으로 주어진다. (h1집과 h2집은 무게제한이 k인 다리로 연결되어 있다.)

출력

숭이의 출발위치에서 혜빈이의 위치까지 숭이가 들고 갈 수 있는 금빼빼로의 최대 개수를 출력하시오.

---

💚나의 풀이

• 전형적인 최소 스패닝 트리 문제이다.
• Edge 클래스 선언 시, 내림차순 가중치 정렬 되게 compareTo() 함수를 재정의해두고, PriorityQueue가 자동 정렬되도록 헀다.
• 처음에는 시작정점 S에 대해 방문처리를 해서 시작하도록 해야하나 고민을 했었는데 그냥 가중치 큰 순으로 하나씩 뽑아서 사이클 형성하지 않도록 union처리를 하다가 문제에서 입력으로 주어졌던 정점 S와 E 사이의 경로가 존재하면 (즉, 둘 사이의 부모가 같다면) 그때의 가중치를 정답 변수에 담은 뒤, break를 걸고 탈출하도록 풀었다.
• 그리고 애초에 PriorityQueue와 compareTo 함수를 통해 가중치가큰 순으로 내림차순 정렬되도록 간선을 처리해두었기 때문에 S와 E를 잇는 가중치는 자동으로 최대값을 갖게 되어있다.
• 다만, 이 문제의 경우 가중치를 경로별로 누적해서 출력하는 방식이 아니라, S에서 E로 갈 때 직전 가중치가 최대이도록 초점만 맞추면 된다.

package to_0925_4;

import java.util.*;
import java.util.Scanner;

/*13905번. 세부 - 최소 스패닝 트리 문풀 */
class Edge implements Comparable<Edge>{
	int s, e , val;
	Edge(int s, int e, int val){
		this.s = s;
		this.e = e;
		this.val =val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return o.val - this.val;//가중치큰 순 내림차순 정렬 
	}
}
public class Main {
	static int N, M;
	static int S, E;
	static int[] parent;
	//find
	static int find(int a) {
		if(a == parent[a]) return a;
		else return parent[a] = find(parent[a]);
	}
	
	//union
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a != b) {
			parent[b] = a;
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		S = kb.nextInt();
		E = kb.nextInt();
		
		parent = new int[N+1];
		for(int i=1; i<=N; i++) parent[i]= i;
	
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		for(int i=0; i<M; i++) {
			//도로 개수만틈 입력받기 
			//양방향 간선임 
			int a = kb.nextInt();
			int b = kb.nextInt();
			int val = kb.nextInt();
			pQ.add(new Edge(a, b, val));
		}
		int useEdge = 0;
		int useCost = 0;
		
        while (!pQ.isEmpty()) {
        	//내림차순 가중치 높은 순으로 차례대로 연결하다가 
            Edge edge = pQ.poll();
            if (find(edge.s) != find(edge.e)) {
                union(edge.s, edge.e);
                //문제에서 주어진 시작점 S와 E의 부모가 같다 = 둘 사이의 경로가 존재 : 이어졌다는 것 
                if(find(S) == find(E)){
                	//어차피 가중치 큰 순으로 하나씩 뽑아 이었기 때문에 
                    useCost = edge.val;//이때의 값이 최대임 
                    break;//탈출 
                }
            }
        }
 
		
		System.out.println(useCost);
	}

}