[백준/Java] 1068 트리

🔗 문제 링크: https://www.acmicpc.net/problem/1068

 

🔍 해결 과정

트리에서 특정 노드를 제거했을 때 그 특정 노드의 자식까지 전부 삭제를 해준 후 남은 리프 노드의 수를 반환하는 문제이므로 다음과 같은 과정을 세웠습니다.

1️⃣ 트리에서 특정 노드가 리프노드인지 확인할 boolean형 배열 isLeaf를 만든다.
2️⃣ 현재 트리에서 리프 노드를 찾아 isLeaf 배열을 수정한다. 아직 이 땐 특정 노드가 제거되지 않은 상태이다.
3️⃣ 수정한 배열 isLeaf를 활용하여 리프 노드이면 리프 노드의 부모를 계속적으로 거스르며 삭제 제거 대상의 노드가 나오는지 탐색한다.
4️⃣ 리프 노드의 부모들 중 제거 대상의 노드가 존재하지 않으면 리프 노드의 개수를 카운트한다.

 

노드의 개수의 최댓값도 50이므로 별다른 시간복잡도 생각을 할 필요도 없어서 편하게 구현할 수가 있었습니다.

---

✏️ 코드

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

public class Main {

    private static final int NONE = -1;
    private static final String SPACE = " ";

    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[] parent = Arrays.stream(br.readLine().split(SPACE))
                .mapToInt(Integer::parseInt)
                .toArray();

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

        boolean[] isLeaf = new boolean[n];
        Arrays.fill(isLeaf, true);
        int leafCount = 0;

        for (int i = 0; i < n; ++i) {
            if (parent[i] == NONE || !isLeaf[parent[i]] || i == removeNumber) {
                continue;
            }

            isLeaf[parent[i]] = false;
        }

        for (int i = 0; i < n; ++i) {
            if (isLeaf[i] && !isRemoveParent(parent, removeNumber, i)) {
                ++leafCount;
            }
        }

        bw.write(Integer.toString(leafCount));
        bw.flush();
        bw.close();
    }

    private static boolean isRemoveParent(final int[] parent,
                                    final int removeNumber, int curNumber) {
        while (curNumber != NONE) {
            if (curNumber == removeNumber) {
                return true;
            }

            curNumber = parent[curNumber];
        }

        return false;
    }
}