[프로그래머스] 388354 홀짝트리 (JavaScript)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/388354

풀이

매번 선호하는 접근 방식으로, 문제를 쭉 읽고 제한 사항을 먼저 확인했다.

nodes의 길이는 최대 $400000$ , edges의 길이는 최대 $1000000$ 이다. 모든 노드를 순회하며 각 노드를 root로 삼아 graph 탐색을 반복한다면, 대충 최대 $400000^2$ 정도의 연산이 필요하므로 시간 초과가 날 것이라 판단했다.

이후 고려한 것은 동적 계획법이었다. 하지만 root를 어떤 노드로 설정하느냐에 따라 부모-자식 관계가 달라지고, 이전 연산 결과를 재활용할 수 없었다. 이 또한 적용 불가능한 알고리즘이라고 판단했다.

보편적인 알고리즘을 바로 적용할 방법이 떠오르지 않아, 이 문제만의 트릭이 있을 것이라 추측하고 문제를 다시 읽어보았다.

홀짝 트리를 만족하려면 다음 조건이 성립해야 한다.

루트 노드는 노드 번호의 홀짝과 차수의 홀짝이 같아야 한다.
- (node & 1) === (degree[node] & 1)
루트가 아닌 모든 노드는 노드 번호의 홀짝과 차수의 홀짝이 달라야 한다.
- (node & 1) !== (degree[node] & 1)

반대로 역 홀짝 트리를 만족하려면 다음 조건이 성립해야 한다.

루트 노드는 노드 번호의 홀짝과 차수의 홀짝이 달라야 한다.
- (node & 1) !== (degree[node] & 1)
루트가 아닌 모든 노드는 노드 번호의 홀짝과 차수의 홀짝이 같아야 한다.
- (node & 1) === (degree[node] & 1)

정리하자면, 하나의 트리가 홀짝 트리가 되려면 노드 번호의 홀짝과 차수의 홀짝이 같은 노드가 정확히 하나 존재해야 한다. 그 노드가 루트가 된다.

반대로 역 홀짝 트리가 되려면 노드 번호의 홀짝과 차수의 홀짝이 다른 노드가 정확히 하나 존재해야 한다. 이 경우에도 해당 노드가 루트가 된다.

따라서, 모든 노드를 루트로 설정해 보며 탐색할 필요가 없고 각 트리의 루트 후보가 정확히 하나 존재하는지만 확인하면 된다.

아이디어를 떠올리는 과정이 어려웠으나 구현 자체는 union-find 알고리즘을 통해 비교적 쉽게 구현할 수 있었다.

보통 stackoverflow 발생 여부를 10만번 이상의 호출로 판단하는데, 해당 로직은 최대 40만번의 호출이 발생할 수 있으므로, 재귀 호출을 통한 union-find 구현은 stackoverflow가 발생할 수 있어 반복문을 통한 union-find 구현으로 변경해야 안전하다.

소스 코드

javascript

const MAX_NODE = 1000000;

const solution = (nodes, edges) => {
    const parent = Array(MAX_NODE + 1).fill(-1);
    const size = Array(MAX_NODE + 1).fill(-1);
    const degree = Array(MAX_NODE + 1).fill(-1);
    
    nodes.forEach(node => {
        parent[node] = node;
        size[node] = 1;
        degree[node] = 0;
    });
    
    const find = (node) => node === parent[node]
        ? node
        : parent[node] = find(parent[node]);
    
    edges.forEach(([ a, b ]) => {
        degree[a] += 1;
        degree[b] += 1;
        
        const pa = find(a);
        const pb = find(b);
        
        if (pa !== pb) {
            parent[pb] = pa;
            size[pa] += size[pb];
        }
    });
    
    const flags = Array(MAX_NODE + 1).fill(0);
    
    nodes.forEach(node => flags[find(node)] += ((node & 1) === (degree[node] & 1)));
    
    return nodes.reduce((acc, node) =>
        node !== find(node)
            ? acc
            : [
                acc[0] + (flags[node] === 1),
                acc[1] + (size[node] - flags[node] === 1)
            ]
    , [0, 0]);
}

[프로그래머스] 388354 홀짝트리 (JavaScript)

문제

풀이

소스 코드

Share this post