홀짝트리 (Java)

📌 문제 설명

• 트리가 주어지고 각 노드의 값은 정수로 이루어져 있다.

• 트리는 두 가지 조건에 따라 홀짝 트리로 구분된다:

  1. 홀짝 트리:

     • 루트 노드를 기준으로 각 노드의 값과 자식 노드의 개수가 같은 홀짝성이어야 한다.
       (예: 루트가 짝수이면 자식 개수도 짝수, 루트가 홀수이면 자식 개수도 홀수)

  2. 역 홀짝 트리:

     • 루트 노드의 값과 자식 노드의 개수의 홀짝성이 반대여야 한다.
       (예: 루트가 짝수이면 자식 개수는 홀수, 루트가 홀수이면 자식 개수는 짝수)

• 모든 노드가 이 규칙을 만족하면 해당 트리를 홀짝 트리 혹은 역 홀짝 트리라고 부른다.

• 트리의 개수와 각 트리가 홀짝 트리와 역 홀짝 트리의 개수를 반환한다.

문제 링크 🔗

---

💡 접근 방법

✅ 첫 번째 시도 (시간 초과)

• 문자열로 홀짝 여부를 저장하고 비교했으나, 문자열 비교로 인해 시간 초과 발생.
• 또한, 부모와 자식의 경우를 모두 체크하는 비효율적인 방식 사용.

---

✅ 두 번째 시도 (성공 - 개수로 비교하여 최적화)

개선 사항:
1. 문자열 비교 제거

• StringBuilder 대신 정수 개수만으로 판단하여 비교 속도를 개선.

2. 두 가지 탐색 함수로 분리

   • checkHolZzak(): 홀짝 트리인지 확인
   • checkReverseHolZzak(): 역 홀짝 트리인지 확인

3. 방문 배열(visited)을 재사용

   • 두 함수는 서로 독립적이므로 visited 배열을 각각 초기화하여 사용.

4. 재귀적 DFS 사용

   • DFS를 통해 모든 노드를 탐색하면서 홀짝성을 검사.
   • 부모 노드를 제외한 자식 노드 수만 계산.

---

🧩 구현 방법

1. 노드와 간선 정보 저장

   • Map<Integer, List<Integer>>을 사용하여 각 노드에 연결된 자식 노드를 저장.

2. DFS로 홀짝성 검사

   • 노드의 값과 자식 수의 홀짝성을 비교하여 규칙에 맞으면 계속 탐색.
   • 규칙에 맞지 않으면 즉시 탐색 종료.

3. 중복 검사 방지

   • visited 배열을 사용하여 중복 검사를 방지.

4. 결과 반환

   • answer[0]: 홀짝 트리의 개수
   • answer[1]: 역 홀짝 트리의 개수

---

🧩 코드 구현

import java.util.*;

class Solution {

    Map<Integer, List<Integer>> trees = new HashMap<>();
    boolean[] visited = new boolean[1000001];

    public int[] solution(int[] nodes, int[][] edges) {
        int[] answer = new int[2];

        // ✅ 1. 노드와 간선 정보 저장
        for (int node : nodes) {
            trees.put(node, new ArrayList<>());
        }
        for (int[] edge : edges) {
            trees.get(edge[0]).add(edge[1]);
            trees.get(edge[1]).add(edge[0]);
        }

        // ✅ 2. 홀짝 트리 검사
        for (int node : nodes) {
            if (!visited[node] && checkHolZzak(node, -1)) {
                answer[0]++; // ✅ 홀짝 트리 개수 증가
            }
        }

        // ✅ 3. 방문 배열 초기화
        visited = new boolean[1000001];

        // ✅ 4. 역 홀짝 트리 검사
        for (int node : nodes) {
            if (!visited[node] && checkReverseHolZzak(node, -1)) {
                answer[1]++; // ✅ 역 홀짝 트리 개수 증가
            }
        }

        return answer;
    }

    // ✅ **홀짝 트리** 검사 (노드의 값과 자식 개수의 홀짝성이 같아야 함)
    private boolean checkHolZzak(int current, int parent) {
        List<Integer> children = trees.get(current);
        int childrenSize = children.size() - 1; // 부모 노드를 제외한 자식 수
        if (parent == -1) {
            childrenSize++; // 루트 노드는 부모가 없으므로 전체 개수 사용
        }

        // ✅ 노드의 값과 자식 수의 홀짝성이 같아야 함
        if (current % 2 == childrenSize % 2) {
            visited[current] = true; // 방문 표시
            for (int child : children) {
                if (child == parent) continue; // 부모 노드는 제외
                if (!checkHolZzak(child, current)) {
                    visited[current] = false;
                    return false; // 하나라도 불일치하면 실패
                }
            }
        } else {
            return false; // 노드의 값과 자식 수의 홀짝성이 다르면 실패
        }
        return true; // 모든 조건을 만족하면 true 반환
    }

    // ✅ **역 홀짝 트리** 검사 (노드의 값과 자식 개수의 홀짝성이 달라야 함)
    private boolean checkReverseHolZzak(int current, int parent) {
        List<Integer> children = trees.get(current);
        int childrenSize = children.size() - 1;
        if (parent == -1) {
            childrenSize++;
        }

        // ✅ 노드의 값과 자식 수의 홀짝성이 달라야 함
        if (current % 2 != childrenSize % 2) {
            visited[current] = true;
            for (int child : children) {
                if (child == parent) continue;
                if (!checkReverseHolZzak(child, current)) {
                    visited[current] = false;
                    return false;
                }
            }
        } else {
            return false;
        }
        return true;
    }
}

---

✅ 알고리즘 설명

1. DFS를 사용하여 모든 노드를 탐색

   • checkHolZzak()와 checkReverseHolZzak()는 각각 한 번씩만 호출되므로 효율적이다.

2. 방문 배열(visited)을 사용하여 중복 탐색 방지

   • 첫 번째 탐색에서는 홀짝 트리만 확인
   • 두 번째 탐색에서는 역 홀짝 트리만 확인

3. 시간복잡도:

   • DFS의 시간복잡도는 O(N)
   • visited 배열을 사용하므로 중복 탐색이 발생하지 않음
   • 따라서 전체 시간복잡도는 O(N)으로 매우 빠름

4. 공간복잡도:

   • Map과 visited 배열을 사용하여 메모리 사용을 최소화
   • 최대 노드 수가 1,000,000이어도 문제없음

---

🧪 테스트 케이스

✅ 기본 테스트

int[] nodes = {1, 2, 3, 4, 5};
int[][] edges = {{1, 2}, {1, 3}, {2, 4}, {2, 5}};
int[] result = solution(nodes, edges);
System.out.println(Arrays.toString(result)); // [1, 0]

---

✅ 역 홀짝 트리 테스트

int[] nodes = {1, 2, 3, 4, 5, 6};
int[][] edges = {{1, 2}, {1, 3}, {3, 4}, {3, 5}, {5, 6}};
int[] result = solution(nodes, edges);
System.out.println(Arrays.toString(result)); // [0, 1]

---

✅ 혼합 테스트

int[] nodes = {1, 2, 3, 4, 5, 6, 7};
int[][] edges = {{1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 6}, {3, 7}};
int[] result = solution(nodes, edges);
System.out.println(Arrays.toString(result)); // [1, 1]

---

✅ 단일 노드 테스트

int[] nodes = {1};
int[][] edges = {};
int[] result = solution(nodes, edges);
System.out.println(Arrays.toString(result)); // [1, 0]

---

💡 문제 해결 과정 요약

1. 첫 번째 시도 (문자열 사용)

   • 문자열 비교와 중복 계산으로 인해 시간 초과 발생

2. 두 번째 시도 (성공 - 최적화)

   • 문자열 제거 및 개수 기반으로 비교하여 속도 개선
   • DFS로 각 노드의 자식 개수와 값을 한 번만 확인
   • visited 배열로 중복 검사 방지

---