작성 코드

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

public class tree_1068 {
    private static void dfs(int num, int[] parent) {
        parent[num] = -2;
        for (int i = 0; i < parent.length; i++) {
            if (parent[i] == num){
                dfs(i, parent);
            }
        }
    }

    private static boolean contains(int[] parent, int num){
        for (int n : parent) {
            if (n == num) {
                return true;
            }
        }
        return false;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int num = Integer.parseInt(st.nextToken());
        int[] parent = new int[num];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < parent.length; i++) {
            parent[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        int delete = Integer.parseInt(st.nextToken());

        dfs(delete, parent);
        int count = 0;
        for (int i = 0; i < parent.length; i++) {
            if (parent[i] != -2 && !contains(parent, i)){
                count++;
            }
        }
        System.out.println(count);
    }
}

설명

해당 코드는 트리 구조에서 노드를 삭제하고 남은 리프 노드의 개수를 세는 문제를 해결하는 코드입니다. 각 부분에 대한 설명은 아래와 같습니다

• dfs 메소드:

  • dfs 메소드는 깊이 우선 탐색(Depth-First Search)을 수행하는 재귀 함수입니다.
  • num은 현재 탐색 중인 노드의 인덱스입니다.
  • parent 배열에서 num 번째 노드의 부모를 -2로 설정하여 삭제된 노드임을 표시합니다.
  • parent 배열을 순회하면서 현재 노드 num을 부모로 가지는 자식 노드들을 재귀적으로 탐색합니다.

• contains 메소드:

  • contains 메소드는 주어진 배열 parent에서 특정 숫자 num이 존재하는지 확인하는 메소드입니다.
  • parent 배열을 순회하며 num과 같은 값이 있는지 확인하고, 존재하면 true를 반환합니다. 그렇지 않으면 false를 반환합니다.

• main 메소드:

  • main 메소드는 프로그램의 진입점입니다.
  • BufferedReader와 StringTokenizer을 사용하여 입력을 받습니다.
  • 첫 번째 줄에서는 트리의 노드 수를 입력받습니다.
  • 두 번째 줄에서는 각 노드의 부모를 나타내는 배열을 입력받습니다.
  • 세 번째 줄에서는 삭제할 노드를 입력받습니다.
  • dfs 메소드를 사용하여 삭제할 노드와 그 자식 노드들을 삭제합니다.
  • count 변수를 사용하여 삭제된 노드가 아니고, 리프 노드인 노드의 개수를 세고 출력합니다.

위의 코드는 입력으로 트리의 노드 수, 각 노드의 부모 정보, 삭제할 노드를 받아 트리를 구성하고, 삭제 후 남은 리프 노드의 개수를 계산합니다. 주어진 입력에 따라 트리를 탐색하고 조건에 맞는 노드들을 삭제하고, 삭제된 노드가 아니고 리프인 노드들의 개수를 세는 방식으로 문제를 해결합니다.

자바스크립트

function dfs(num, parent) {
  parent[num] = -2;
  for (let i = 0; i < parent.length; i++) {
    if (parent[i] === num) {
      dfs(i, parent);
    }
  }
}

function contains(parent, num) {
  for (let n of parent) {
    if (n === num) {
      return true;
    }
  }
  return false;
}

function main() {
  const readline = require("readline");
  const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
  });

  rl.question("Enter the number: ", (num) => {
    const parent = new Array(num);
    rl.question("Enter the parent array: ", (parentInput) => {
      const parentTokens = parentInput.trim().split(" ");
      for (let i = 0; i < parent.length; i++) {
        parent[i] = parseInt(parentTokens[i]);
      }
      rl.question("Enter the delete node: ", (deleteInput) => {
        const deleteNode = parseInt(deleteInput);

        dfs(deleteNode, parent);
        let count = 0;
        for (let i = 0; i < parent.length; i++) {
          if (parent[i] !== -2 && !contains(parent, i)) {
            count++;
          }
        }
        console.log(count);
        rl.close();
      });
    });
  });
}

main();

파이썬

import sys
input = sys.stdin.readline

def dfs(num, parent):
    parent[num] = -2
    for i in range(len(parent)):
        if parent[i] == num:
            dfs(i, parent)

num = int(input())
parent = list(map(int, input().split()))
delete = int(input())

dfs(delete, parent)
count = 0
for j in range(len(parent)):
    if parent[j] != -2 and j not in parent:
        count += 1
print(count)