[백준] 1647.도시분할계획 (java) / 크루스칼, Union-Find

@크루스칼, Union-Find / 51m

시간이 계속 터져서, 15분정도 고쳤다.

쉬운 문제인데 너무 어렵게 생각해서 좀 돌아갔다.

 

 

 

문제 링크

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

1647번: 도시 분할 계획

 

구현 포인트

처음에는 배열에 값을 받고, Arrays.sort()로 정렬했는데

우선순위 큐로 다시 풀어보니 시간이 1초 이상 줄었다. (배열로 풀어도 통과하기는 한다.)

 

 

우선순위 큐를 이용해서 푼 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	private static class Node implements Comparable<Node> {
		int s, e, v;
		Node (int s, int e, int v) {
			this.s = s;
			this.e = e;
			this.v = v;
		}
		@Override
		public int compareTo(Node o) {
			return this.v - o.v;
		}
	}
	
	private static int N, M, min, parents[];
	private static PriorityQueue<Node> pq;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		pq = new PriorityQueue<>();
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			pq.add(new Node(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken())));
		}
		
		parents = new int[N];
		Arrays.fill(parents, -1);
		
		wayMake();
		System.out.println(min);
	}

	private static void wayMake() {
		int num = 0;
		while (!pq.isEmpty()) {
			Node temp = pq.poll();
			if (union(temp.s, temp.e)) {
				min += temp.v;
				num++;
			}
			
			if (num == N - 2) return;
		}
	}

	private static boolean union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		if (aRoot != bRoot) {
			parents[bRoot] = aRoot;
			return true;
		}
		return false;
	}

	private static int find(int a) {
		if (parents[a] < 0)
			return a;
		return parents[a] = find(parents[a]);
	}
}

맨 위 코드가 우선순위 큐로 푼 코드, 아래 코드가 배열로 푼 코드

 

삽질 포인트

1. 처음에는 조합으로 마을 조합의 경우를 다 구한 뒤 union-find를 돌려서 최소 값을 찾게끔 풀었는데 시간초과가 떴다.

 

2. 그 다음번에 그냥 낮은 가중치 부터 union-find를 돌리고, parents[i] < 0 인 갯수가 2개면 끝나게 하면 된다는걸 깨달았다.

그래서 union-find가 끝날때마다 parents 배열을 체크해주는 함수를 돌렸는데 그래도 시간초과가 떴다.

 

3. 고민하다가 parents배열을 체크하는 함수를 빼고, union이 true일때마다 num++을 해줘서 num을 체크하도록 로직을 바꿨더니 통과했다.

 

 

 

크루스칼은 !pq.isEmpty() 동안 돌려도 되지만, 사실 정확하게는 간선의 개수 < 정점의 개수 - 1 동안 돌리는게 더 정확하고 빠르다.

그 점을 깨달을 수 있는 문제였다.

 

끝!