백준 | 21924번. 도시 건설 - 최소비용 신장 트리

⬛ 백준 21924번. 도시 건설 - 최소비용 신장 트리

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

21924번: 도시 건설

문제

채완이는 신도시에 건물 사이를 잇는 양방향 도로를 만들려는 공사 계획을 세웠다.

공사 계획을 검토하면서 비용이 생각보다 많이 드는 것을 확인했다.

채완이는 공사하는 데 드는 비용을 아끼려고 한다.

모든 건물이 도로를 통해 연결되도록 최소한의 도로를 만들려고 한다.

그림에 있는 도로를 다 설치할 때 드는 비용은 62이다. 모든 건물을 연결하는 도로만 만드는 비용은 27로 절약하는 비용은 35이다.

채완이는 도로가 너무 많아 절약되는 금액을 계산하는 데 어려움을 겪고 있다.

채완이를 대신해 얼마나 절약이 되는지 계산해주자.

입력 설명

출력

예산을 얼마나 절약 할 수 있는지 출력한다. 만약 모든 건물이 연결되어 있지 않는다면 -1을 출력한다.

---

💚나의 풀이

풀이 설명

• 이 문제에서 주의해야 할 점은 크게 두 가지가 있다.

1) 첫 번째로 데이터의 크기가 매우 크기 때문에 정답에 사용될 변수는 long 타입으로 선언해야 하는 점이다.

2) 두 번째로 ‘모든 건물이 연결되어 있지 않다’는 것을 어떤 식으로 해결할 것이냐이다.

• 처음에는 parent[] 배열에서 각 정점들의 부모가 다르면 모든 건물이 연결되지 않은 것이라고 풀려고 시도했다.
• 콘솔창에서는 일반 케이스에 대한 답은 나오지만, 단절된 케이스의 경우 while문에서 사용 간선 수가 N-1이 되기 전에 pQ상에 처리할 다음 정점이 존재 하지 않아서 NullPointerException이 뜨는 문제가 있다.
• 따라서, while문 안에서 단절점이 생겨 pQ에 다음 처리할 정점이 존재하지 않을 경우를 대비해야 한다.

아래의 코드를 보게 되면 while문 내부에서 사용 간선이 N-1이 되기도 전에 다음 처리할 간선이 null이 되면 flag 를 true로 걸어두고 탈출하도록 짰다.

이 상태가 다음 연결할 정점이 끊어져서 = 모든 건물이 연결되지 않은 상태이다.

while(useEdge < N-1) {
			Edge cur = pQ.poll();
			//그런데 만약 N-1되기 전에 다음 정점이 존재하지 않는다면
			if(cur==null && useEdge < N-1) {
				flag = true;
				break;//탈출
			}
			
			if(find(cur.s) != find(cur.e)) { //사이클 형성 하지 않도록 
				union(cur.s, cur.e);
				useCost += cur.val;
				useEdge++;
			}
		}

---

💚 제출 코드

package to_0906_D;

import java.util.PriorityQueue;
import java.util.Scanner;

/*백준 21924번. 도시 건설- 최소 비용 신장 트리 */
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 this.val - o.val;
	}
}
public class Main {
	static int[] parent;
	static int N, M;
	//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();
		
		parent = new int[N+1];
		for(int i=1; i<=N; i++) parent[i] = i;
		
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		long total = 0;//전체 비용 합계
		for(int i=0; i<M; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int c = kb.nextInt();
			pQ.offer(new Edge(a, b, c));
			total += c;
		}
		boolean flag = false;
		//최소신장트리 로직 시작 
		int useEdge = 0;
		// 여기 데이터 크기가 다 개 크니까 long 타입으로 선언할 것 !!!!!!!!!!!!
		long useCost = 0;
		while(useEdge < N-1) {
			Edge cur = pQ.poll();
			//그런데 만약 N-1되기 전에 다음 정점이 존재하지 않는다면
			if(cur==null && useEdge < N-1) {
				flag = true;
				break;//탈출
			}
			
			if(find(cur.s) != find(cur.e)) { //사이클 형성 하지 않도록 
				union(cur.s, cur.e);
				useCost += cur.val;
				useEdge++;
			}
		}
		
		if(flag == true) System.out.println("-1");
		else System.out.println(total - useCost);
	}
}