b1068. 트리

 

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

 

 

 

🌲 자바로 푸는 트리 문제 풀이 (백준 1068 - 트리)

 

---

 

📌 문제 개요

 

• N개의 노드로 이루어진 트리가 주어짐
• 노드 중 하나를 삭제했을 때, 남은 트리의 리프 노드 개수를 구하는 문제

 

 

제약 조건

 

• 트리의 노드는 0번부터 N-1번까지
• 루트는 부모가 -1인 노드
• 삭제 시 해당 노드와 그 하위 노드 전부 제거

 

---

 

💡 예제 입력

5
-1 0 0 1 1
2

→ 노드 2번을 지우면, 남은 트리 구조는 다음과 같다:

        0
       / \
      1   (X)
     / \
    3   4

→ 리프 노드는 3, 4 → 2개

 

 

예제 출력

2

 

---

 

🧠 알고리즘 접근 방식

 

1. 입력 배열을 기반으로 트리 구조 생성
   • tree[i] = [자식1, 자식2, ...]
2.  
3. 삭제할 노드가 루트면 → 리프 노드 0개
4. 루트부터 DFS 수행
   • 자식이 없거나 삭제된 자식만 있으면 리프 노드로 간주
5.  

 

---

 

🔁 전체 코드 (DFS 기반)

import java.util.*;

public class Main {
    static List<Integer>[] tree;
    static int deleteNode, leafCount = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] parent = new int[N];
        tree = new ArrayList[N];
        int root = -1;

        for (int i = 0; i < N; i++) tree[i] = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            parent[i] = sc.nextInt();
            if (parent[i] == -1) root = i;
            else tree[parent[i]].add(i);
        }

        deleteNode = sc.nextInt();

        if (deleteNode == root) System.out.println(0);
        else {
            dfs(root);
            System.out.println(leafCount);
        }
    }

    static void dfs(int now) {
        if (now == deleteNode) return;

        int childCount = 0;
        for (int child : tree[now]) {
            if (child != deleteNode) {
                dfs(child);
                childCount++;
            }
        }

        if (childCount == 0) leafCount++;
    }
}

 

---

 

🔍 코드 해설

구문	설명
tree[parent[i]].add(i)	트리를 자식 기준으로 구성
if (deleteNode == root)	루트가 지워지면 트리 자체가 사라짐
dfs(now)	삭제 노드를 만나면 바로 리턴
if (childCount == 0)	더 이상 갈 자식이 없다면 리프 노드

 

---

 

✅ 핵심 포인트 정리

 

• 트리는 연결 정보가 명시적으로 주어지지 않음 → 부모 배열 기반으로 자식 리스트 생성
• 삭제되는 노드가 루트일 경우 주의!
• DFS 중 삭제 대상 노드는 방문하지 않음