[programmers/js] 홀짝트리

홀짝 트리

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

문제 설명

여러 개의 노드와 간선으로 이루어진 포레스트(여러 개의 트리)가 주어집니다.

각 노드는 다음 4가지 중 하나로 분류

노드 번호	자식 수	분류
홀수	홀수	홀수 노드
짝수	짝수	짝수 노드
홀수	짝수	역홀수 노드
짝수	홀수	역짝수 노드

홀짝 트리
트리 안의 노드가 전부 "홀수/짝수 노드"로만 이루어짐

역홀짝 트리
트리 안의 노드가 전부 "역홀수/역짝수 노드"로만 이루어짐

트리마다 루트를 다르게 설정할 수 있으므로, 루트를 어떤 노드로 하느냐에 따라 트리의 성질이 달라질 수 있습니다.

풀이

이 문제는 각 트리(포레스트의 구성요소)가 루트 선택에 따라 어떤 성질을 갖는지 파악하는 문제로 우리는 노드마다 번호의 홀짝, 연결된 자식 수의 홀짝 이 두 조건을 비교하여 루트로 삼을 수 있는지 판단해야 합니다.

초기 세팅
Union-Find에서 사용하는 parent 배열 초기화
parent[i] = i 로 자기 자신이 부모인 상태로 시작

const N = nodes.length
const parent = Array(N).fill(0).map((_, i) => i);

Union-Find 정의

const find = (a) => { ... }  // 경로 압축
const union = (a, b) => { ... }  // 루트 연결

노드 번호 <-> 인덱스 매핑 & 차수 계산
실제 값 (예: 11, 3, 9 ...) 을 index로 변환해 배열 기반으로 관리

const nodeToIndex = new Map();
const degree = Array(N).fill(0);
nodes.forEach((node, idx) => nodeToIndex.set(node, idx));

각 노드의 자식 수 (차수) 를 구함

edges.forEach(([x, y]) => {
  const u = nodeToIndex.get(x);
  const v = nodeToIndex.get(y);
  degree[u] += 1;
  degree[v] += 1;
});

트리 구성 (간선 기반 Union)

edges.forEach(([x, y]) => {
  const u = nodeToIndex.get(x);
  const v = nodeToIndex.get(y);
  union(u, v);
});

노드 분류 – 홀짝 노드 / 역홀짝 노드
각 트리의 루트 기준으로 해당 노드가 어떤 유형인지 판별
1. node와 자식 수의 홀짝이 같으면 → rootGroup
2. 다르면 → nonRootGroup

const rootGroup = Array(N).fill(0); // 홀짝 노드 수
const nonRootGroup = Array(N).fill(0); // 역홀짝 노드 수

nodes.forEach((node, idx) => {
  const v = find(idx); // 대표 노드
  if ((node % 2) === (degree[idx] % 2)) rootGroup[v] += 1;
  else nonRootGroup[v] += 1;
});

루트 후보 수 검사
루트가 여러 명이면 결과가 달라질 수 있어 트리마다 루트가 될 수 있는 노드" 정확히 1개일 때만 정답 카운트

for (let i = 0; i < N; i++) {
  if (find(i) !== i) continue; // 루트 노드가 아니면 패스

  if (rootGroup[i] === 1) hTreeCount++;
  if (nonRootGroup[i] === 1) rTreeCount++;
}

최종 코드

function solution(nodes, edges) {
    const N = nodes.length
    const parent = Array(N).fill(0).map((_, i) => i);
    
    const find = (a) => {
        if (parent[a] === a) return a;
        return parent[a] = find(parent[a]);
    }
    
    const union = (a, b) => {
        const rootA = find(a);
        const rootB = find(b);
        
        if (rootA !== rootB) {
            parent[rootB] = rootA
        }
    }
    
    // 각 노드들의 자식 수 알아야 함
    const nodeToIndex = new Map();
    const degree = Array(N).fill(0);
    nodes.forEach((node, idx) => nodeToIndex.set(node, idx));

    edges.forEach(([x, y]) => {
        const u = nodeToIndex.get(x);
        const v = nodeToIndex.get(y);
        degree[u] += 1
        degree[v] += 1
    });

    edges.forEach(([x, y]) => {
        const u = nodeToIndex.get(x);
        const v = nodeToIndex.get(y);
        union(u, v);
    });
    
    const rootGroup = Array(N).fill(0); // 루트 그룹 카운트 초기화
    const nonRootGroup = Array(N).fill(0); // 비루트 그룹 카운트 초기화
    
    nodes.forEach((node, idx) => {
        const v = find(idx);
        if ((node % 2) === (degree[idx] % 2)) rootGroup[v] += 1;
        else nonRootGroup[v] += 1;
    })
    
    let hTreeCount = 0; // 홀짝 트리 카운트
    let rTreeCount = 0; // 역홀짝 트리 카운트

    for (let i = 0; i < N; i++) {
        if (find(i) !== i) continue;

        if (rootGroup[i] === 1) hTreeCount++;
        if (nonRootGroup[i] === 1) rTreeCount++;
    }
    return [hTreeCount, rTreeCount];
}

참고 자료

• https://jaimemin.tistory.com/2633#google_vignette