1068번: 트리

문제

트리가 주어지고, 그중 하나의 노드를 지웠을 때 남은 트리에서 리프 노드(단말 노드)의 개수를 구하는 문제입니다. 노드를 지우면 그 노드와 해당 노드를 루트로 하는 모든 하위 서브 트리도 함께 지워집니다.

• 입력:
  • 첫째 줄에 트리의 노드 개수 N (1 ≤ N ≤ 50)이 주어집니다.
  • 둘째 줄에 0번 노드부터 N-1번 노드까지 각 노드의 부모가 주어집니다. (부모가 없으면 -1)
  • 셋째 줄에 지울 노드의 번호가 주어집니다.
• 출력: 주어진 노드를 지운 후 남은 트리에서 리프 노드의 개수를 출력합니다.

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

풀이 1: BFS 탐색과 예외 처리

이 문제는 그래프(트리) 탐색 중에 지워질 노드를 만나면 탐색을 건너뛰는 방식으로 해결할 수 있습니다. 큐(Queue)를 활용한 너비 우선 탐색(BFS) 방식입니다.

1. 트리 구성: 주어진 부모-자식 관계를 바탕으로 양방향 인접 리스트(adj)를 만듭니다. (부모 노드가 -1인 경우는 루트 노드이므로 따로 root 변수에 저장합니다.)
2. 루트 노드 삭제 예외 처리: 만약 지워야 할 노드(rm)가 루트 노드 자체라면, 트리가 통째로 날아가게 되므로 리프 노드는 0개가 됩니다. 이 경우 탐색할 필요 없이 곧바로 0을 출력하고 종료합니다.
3. BFS 탐색 및 리프 노드 판별:
   • 큐에 루트 노드를 넣고 탐색을 시작합니다.
   • 현재 노드(x)와 연결된 다음 노드(nx)들을 확인합니다.
   • 삭제 처리: 만약 다음 노드가 지워야 할 노드(nx == rm)이거나 이미 방문한 노드(부모 노드)라면 큐에 넣지 않고 건너뜁니다.
   • 리프 노드 판별: 유효한 자식 노드를 하나라도 발견했다면 flag를 true로 설정하고 큐에 넣습니다. 만약 반복문이 끝날 때까지 flag가 false라면 (자식이 없거나, 있던 자식이 삭제될 노드라서 무시된 경우), 해당 노드는 리프 노드이므로 cnt를 1 증가시킵니다.

코드 1 (BFS)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       // 노드 개수 입력
       int n = Integer.parseInt(br.readLine());
       int root = -1;
       
       // 인접 리스트 초기화
       List<List<Integer>> adj = new ArrayList<>();
       for (int i = 0; i < n; i++) {
          adj.add(new ArrayList<>());
       }

       // 트리 구조 입력
       StringTokenizer st = new StringTokenizer(br.readLine());
       for (int i = 0; i < n; i++) {
          int x = Integer.parseInt(st.nextToken());
          if (x == -1) {
             root = i; // 부모가 -1이면 루트 노드
             continue;
          }

          // 무방향(양방향) 간선 연결
          adj.get(x).add(i);
          adj.get(i).add(x);
       }

       // 지울 노드 번호 입력
       int rm = Integer.parseInt(br.readLine());

       // 지울 노드가 루트라면 트리가 완전히 지워지므로 리프 노드는 0개
       if (rm == root) {
          bw.write("0");
       } else {
          Queue<Integer> q = new LinkedList<>();
          boolean[] visited = new boolean[n];
          
          q.add(root);
          visited[root] = true;

          int cnt = 0; // 리프 노드 개수 카운트
          
          // BFS 탐색
          while (!q.isEmpty()) {
             boolean flag = false; // 자식 노드가 존재하는지 확인하는 플래그
             int x = q.poll();
             
             for (int nx : adj.get(x)) {
                // 이미 방문한 곳(부모 노드)은 무시
                // 지워야 할 노드라면 탐색에서 제외(서브트리 단절)
                if (visited[nx] || nx == rm)
                   continue;
                   
                flag = true; // 유효한 자식 노드가 존재함
                q.add(nx);
                visited[nx] = true;
             }

             // 유효한 자식 노드가 하나도 없다면 리프 노드임
             if (!flag) {
                cnt++;
             }
          }

          bw.write(cnt + "");
       }

       bw.flush();
    }
}

풀이 2: DFS (깊이 우선 탐색) 재귀 활용

재귀 함수를 활용하면 큐(Queue) 없이도 트리 구조를 탐색할 수 있습니다. 부모-자식 관계가 명확한 트리 문제에서는 DFS가 종종 더 간결한 코드를 만들어냅니다.

1. DFS 재귀 설계: 현재 노드에서 방문할 수 있는 모든 유효한 자식 노드(nx)에 대해 dfs 함수를 재귀 호출합니다.
2. 자식 개수 파악: 재귀 호출을 할 때마다 childCount를 증가시킵니다. (지워진 노드이거나 이미 방문한 노드라면 카운트하지 않습니다.)
3. 리프 노드 반환: 탐색을 마쳤는데 childCount가 0이라면, 자신에게 달린 자식이 하나도 없다는 뜻이므로 리프 노드입니다. 이때 1을 반환하고, 자식이 있다면 자식들로부터 반환받은 리프 노드들의 합(leafCount)을 위로 올려보냅니다.

코드 2 (DFS)

import java.io.*;
import java.util.*;

public class Main {
    static List<List<Integer>> adj = new ArrayList<>();
    static boolean[] visited;
    static int rm;

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int n = Integer.parseInt(br.readLine());
       int root = -1;
       
       for (int i = 0; i < n; i++) {
          adj.add(new ArrayList<>());
       }

       StringTokenizer st = new StringTokenizer(br.readLine());
       for (int i = 0; i < n; i++) {
          int x = Integer.parseInt(st.nextToken());
          if (x == -1) {
             root = i;
             continue;
          }
          adj.get(x).add(i);
          adj.get(i).add(x);
       }

       rm = Integer.parseInt(br.readLine());

       if (rm == root) {
          bw.write("0");
       } else {
          visited = new boolean[n];
          // 루트 노드부터 DFS 탐색 시작 및 결과 출력
          bw.write(dfs(root) + "");
       }

       bw.flush();
    }

    static int dfs(int node) {
        visited[node] = true;
        int childCount = 0; // 유효한 자식 노드의 개수
        int leafCount = 0;  // 현재 노드를 루트로 하는 서브트리의 리프 노드 합계

        for (int next : adj.get(node)) {
            // 방문했던 노드(부모)이거나, 삭제될 노드라면 탐색 생략
            if (visited[next] || next == rm) continue;
            
            childCount++;
            // 자식 노드가 가진 리프 노드 개수를 누적
            leafCount += dfs(next);
        }

        // 유효한 자식 노드가 하나도 없다면 자기 자신이 리프 노드임
        if (childCount == 0) {
            return 1;
        }
        
        return leafCount;
    }
}

알고리즘 분류

그래프 탐색, 트리, 너비 우선 탐색 (BFS), 깊이 우선 탐색 (DFS)