[백준 1068] 트리 - JAVA

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

 

트리에서 노드를 하나 끊었을 때 리프 노드의 개수를 구하는 문제

 

1. 루트 노드 정하기

트리에서 부모가 없는 노드는 유일하며, 루트 노드가 된다

 

(루트 노드를 어디로 잡냐에 따라 리프 노드 개수 또한 달라진다.)

(어디던 루트로 잡아도 되지않나 해서 모호했는데, 문제에서 "연결된 노드" 가 아니라 "부모 노드" 목록이 주어진다.)

 

2. 노드 끊는법 정하기

단순히 방문처리(vst[REMOVE] = true)한다.

이러면 끊은 노드 및 서브 트리를 방문하지 않게된다.

 

+ 문제에선 한 개의 노드만 끊는다.

 

3. 리프 노드 기준 정하기

vst[next] = false 일 때만 다음 탐색을 진행한다.

다음 탐색을 한 번도 하지 않았다면 이는 곧 리프 노드다.

 

4. 예외 처리

문제에서, 루트 노드를 끊으면 트리 전체가 사라진 취급한다. (리프 노드 또한 0개다.)

모든 탐색에서 bfs시 vst[ROOT] = true를 하고 시작하므로, 이 경우는 따로 처리해준다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int ROOT = -1;
    int leaf = 0;
    int N = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());

    List<Integer>[] edge = new ArrayList[N];
    for (int i = 0; i < N; i++) {
      edge[i] = new ArrayList<>();
    }

    for (int i = 0; i < N; i++) {
      int e = Integer.parseInt(st.nextToken());

      if (e == -1) {
        ROOT = i;
      } else {
        edge[e].add(i);
      }
    }

    int REMOVE = Integer.parseInt(br.readLine());

    if (REMOVE == ROOT) {
      System.out.println(0);
      return;
    }

    boolean[] vst = new boolean[N];
    Queue<Integer> q = new ArrayDeque<>();
    vst[ROOT] = true;
    vst[REMOVE] = true;
    q.offer(ROOT);

    while (!q.isEmpty()) {
      int node = q.poll();
      boolean isLeaf = true;

      for (int next : edge[node]) {
        if (!vst[next]) {
          vst[next] = true;
          q.offer(next);
          isLeaf = false;
        }
      }

      if (isLeaf) {
        leaf++;
      }
    }

    System.out.println(leaf);
  }
}