[백준/유니온파인드] 20040번. 사이클게임(JavaScript)

문제

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

 

풀이

게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다.

몇번째 차례에서 사이클이 완성되었는지, 혹은 아직 게임이 진행중인지 판단하는 문제이다.

 

즉, 지금까지 그린 선분이 사이클이 이뤄진 것인지 판단하는 문제이다.

현재 제공되는 두 개의 노드의 부모가 같은지 (=하나의 집합인지) 보면 해결되는 유니온 파인드 문제이다.

 

알고리즘은 다음과 같다.

노드와 노드를 잇기 전에 두 개가 같은 그래프 내에 속해 있는지 두 노드의 부모노드를 확인한다.

부모노드가 같다면 몇 번째 차례에서 완성되었는지 출력한다.

부모노드가 다르다면, 각각의 부모노드를 구한다음 더 작은 값 쪽으로 부모를 합쳐준다. 

 

코드는 다음과 같다.

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split('\n');
let [N, M] = input.shift().toString().split(' ').map(Number);

// 부모노드를 찾는 함수
function getParent(parent, x) {
    if (parent[x] === x) return x;
    return parent[x] = getParent(parent, parent[x]);
}

// 두 부모노드를 합치는 함수
function unionParent(parent, a, b) {
    a = getParent(parent, a);
    b = getParent(parent, b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}

// 같은 부모를 가지는지 확인
function findParent(parent, a, b) {
    a = getParent(parent, a);
    b = getParent(parent, b);
    if (a == b) return 1;
    return 0;
}

function solution(N, M) {
    let parent = [];
    // 자기자신을 부모로 설정
    for (let i = 0; i < N; i++) {
        parent[i] = i;
    }

    for (let i = 0; i < M; i++) {
        let [a, b] = input[i].toString().split(' ').map((el) => parseInt(el, 10));
        if (findParent(parent, a, b)) {
            return i + 1;
        }
        unionParent(parent, a, b);
    }
    return 0;
}

console.log(solution(N, M));

 

예시에 따른 코드 진행은 다음과 같다.

 

참고

안경잡이 개발자 - Union Find

https://m.blog.naver.com/ndb796/221230967614