UnionFind(합집합 찾기) 알고리즘

 

class UnionFind{
	constructor(size){
    	this.parent = Array.from({length:size}, (_, i)=>i)
    }

	find(x){
    	if(this.parent[x] === x){
        	return x;
        }
        return (this.parent[x] = this.find(this.parent[x]));   //부모의 값을 넣음으로써 경로 단축
    }
  
 	union(x, y){
    	const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX !== rootY){
        	this.parent[rootX] = rootY;
        }
    }
}

 

 

< 기본 로직 >

union으로 연결하고 싶은 노드들을 연결 한뒤 나중에 찾을땐 find 함수로 연결 되어 있는지 (합집합 인지) 검사한다.

 

union 함수

연결하고자 하는 두 x, y의 원소가 서로 다르면 rootY(오른쪽값)으로 설정한다.

 

Find 함수

 

return (this.parent[x] = this.find(this.parent[x]));   

 

//위 부분이 핵심인데, 최초에 탐색할 때 부모의 값으로 해당 키값을 갱신한다.
이러면 다음부턴 탐색할 땐 경로를 단축하게 해준다.

 

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

해당문제에 사용했으며 전체적인 코드는 아래와 같다

 

const inputFile = process.platform === "linux" ? "/dev/stdin" : "./example.txt";

const input = require("fs")

    .readFileSync(inputFile)

    .toString()

    .trim()

    .split("\n");

let index = 0;

let cities = Number(input[index++].trim());

let count = Number(input[index++].trim());

class UnionFind {

    constructor(size) {

        this.parent = Array.from({ length: size }, (_, i) => i);

    }

    find(x) {

        if (this.parent[x] === x) {

            return x;

        }

        return (this.parent[x] = this.find(this.parent[x]));

    }

    union(x, y) {

        const rootX = this.find(x);

        const rootY = this.find(y);

        if (rootX !== rootY) {

            this.parent[rootX] = rootY;

        }

    }

}

const map = [];

for (let i = 0; i < count; i++) {

    map.push(input[index++].trim().split(" ").map(Number));

}

const plan = input[index].trim().split(" ").map(Number);

const uf = new UnionFind(cities);

for (let i = 0; i < cities; i++) {

    for (let j = 0; j < cities; j++) {

        if (map[i][j] === 1) uf.union(i, j);

    }

}

function isPlanValid(plan) {

    const start = plan[0] - 1;

    for (let i = 1; i < plan.length; i++) {

        const nextCity = plan[i] - 1;

        if (uf.find(start) !== uf.find(nextCity)) return false;

    }

    return true;

}

console.log(isPlanValid(plan) ? "YES" : "NO");