PGMS 전력망을 둘로 나누기

https://programmers.co.kr/learn/courses/30/lessons/86971

코딩테스트 연습 - 전력망을 둘로 나누기

function solution(n, wires) {
	var answer = -1;
	let min = Math.max;
	let root = [];
	for (let j = 0; j < wires.length; j++) {
		root = [];
		for (let i = 0; i <= n; i++) {
			root.push(i);
		}
		wires.forEach(([x, y], k) => {
			if (k != j) union(x, y);
		});
		let cnt = 1;
		for (let i = 2; i <= n; i++) {
			let iroot = find(i);
			if (iroot == find(1)) {
				cnt++;
			}
		}
		let rest = n - cnt;
		cnt = Math.abs(cnt - rest);
		min = min < cnt ? min : cnt;
	}

	return min;

	function union(x, y) {
		let xroot = find(x);
		let yroot = find(y);
		if (yroot > xroot) root[yroot] = xroot;
		else root[xroot] = yroot;
	}

	function find(x) {
		if (root[x] == x) {
			return x;
		} else {
			return (root[x] = find(root[x]));
		}
	}
}

Union Find를 통해서 해결하였다.

 

문제해결 아이디어는

 

1. 반복문을 돌면서 wire 하나씩 제외하고 Union Find

2. 이후 구한 Parent(여기서는 root)에서 첫번쨰 요소와 같은 개수를 구함

 

Union Find를 함수로 묶는게 더 깔끔했을것 같다.

 

오롯이 자기 힘으로 유니온 파인드 문제를 푼게 처음이라 기분이 좋다.