[백준] 1717: 집합의 표현 - JS (Union-Find)

  목 차

• 문제
• 접근 방식
  • answer 배열이 필요하다!
• 풀이

 

---

  문제

 

 

 

  접근 방식

 

이 문제는 Union-Find / Disjoint-Set문제이다.

 

이 문제에서는 parent 배열과 rank 배열(최적화), 그리고 *answer 배열(JS만 필요한 듯)이 필요하다.

answer 배열이 필요한 이유는 접근 방식 챕터의 가장 마지막에 작성하도록 하겠다.

 

랭크 시스템을 적용하지 않은 Union-Find 알고리즘은 구현하기 쉬운데 Find와 Union 함수를 구현하면 된다.

 

Find: 숫자를 받아오고 계속 타고 올라간다. 올라가면서 num과 parent[num]이 같지 않다면 가장 조상의 인덱스 번호로 바꿔준다.

function find(num){
    if(num !== parent[num]){
        parent[num] = find(parent[num]);
    }
    return parent[num];
}

 

Union: num1과 num2는 각각 a, b의 조상이다.

a, b: operation(0 or 1), a, b 형태로 입력이 들어옴.

만약 num1과 num2가 같지 않다면 조상이 같지 않다는 뜻이므로, 같은 집합에 있지 않다는 의미이다.

그러므로 합쳐주어야 하는데, 랭크 시스템이 없다면 그냥 다음과 같이 작성하여 간단하게 하면된다.

parent[num2] = num1;

 

하지만 이렇게 한다면 트리 구조가 1자가 되어서 시간 복잡도가 굉장히 크게 된다.

그래서 랭크 시스템을 적용하면 아래와 같은 코드가 완성된다. 

 

랭크 배열이 필요한데 길이가 N인 배열에 초기 랭크는 모두 0이다.

function union(a, b){
    const num1 = find(a);
    const num2 = find(b);

    if(num1 !== num2){
        if(rank[num1] > rank[num2]){  // 랭크 부분
            parent[num2] = num1;
        } else {
            parent[num1] = num2;
            if(rank[num1] == rank[num2]){  // 랭크 부분
                rank[num2]++;
            }
        }
    }
}

 

  Rank가 같을 때만 rank를 ++ 한다고..?

 

다음과 같이 집합 A와 집합 B 가 존재한다고 해보자.

두 집합의 랭크는 각각 2와 1이다.

여기서 집합 A와 집합 B를 합친다고 하면, B를 A에 합치게 될 것이다.

그러면 너비는 늘어가는 방면에 깊이는 증가하지 않는다.

하지만 A와 B의 랭크가 같다면 그 아래 노드가 생기니 깊이 역시 1이 증가한다.(아래 이미지 참고)

여기까지 하면 Union-Find 알고리즘 구현은 끝났다.

 

 

  answer 배열이 필요하다!

 

answer 배열이 없이 이 문제를 풀고 나면 시간이 미친 듯이 뻥튀기되어있는 장면을 볼 수 있다. 

처참한 장면

그래서 나는 이런저런 시도를 해보다가 마지막 두 번에서 이유를 찾았다.

 

가장 위에 두 풀이의 차이점은 answer 배열에 저장하고 나중에 출력을 하느냐, 저장하지 않고 바로 출력을 하느냐의 차이이다.

이 시간 차이는 JS의 출력 방식 때문에 발생하는데, 자바스크립트는 데이터를 연속적으로 전송하는 스트림 방식이 아닌, 스택 형식을 사용하여 'console' 출력을 계속해서 따로 호출하는 방식이기 때문이다.

 

위 글을 쉽게 말하자면,

자바스크립트는 출력할 때마다 출력 명령을 새로 실행하기 때문에, 많은 양의 데이터를 출력할 때는 비효율적일 수 있다.

 

 

  풀이

 

const fs = require('fs');
const input = fs.readFileSync(0).toString().trim().split('\n');

const [N, M] = input[0].split(' ').map(Number);

const nodes = [];
const parent = [];
const rank = [];
const answer = [];

for(let i = 0; i <= N; i++){
    parent[i] = i;
    rank[i] = 0;
}

for(let i = 1; i <= M; i++){
    nodes.push(input[i].split(' ').map(Number));
}

function find(num){
    if(num !== parent[num]){
        parent[num] = find(parent[num]);
    }
    return parent[num];
}

function union(a, b){
    const num1 = find(a);
    const num2 = find(b);

    if(num1 !== num2){
        if(rank[num1] > rank[num2]){
            parent[num2] = num1;
        } else {
            parent[num1] = num2;
            if(rank[num1] == rank[num2]){
                rank[num2]++;
            }
        }
    }
}

nodes.forEach(([Check, a, b]) => {
    if(Check == 0){
        union(a, b);
    } else {
        answer.push(find(a) === find(b) ? 'YES' : 'NO');
    }
});

console.log(answer.join('\n'));