[BOJ/JAVA] 1068번: 트리

1068번: 트리

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

키워드

트리가 주어졌을 때, 노드 하나를 지울 것이다.

그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오.

노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

---

구현

private static int solution()

노드를 돌면서 리프 노트의 갯수를 반환하는 메소드

• 방문할 노드를 찾기
  • tree[i] 값은 i노드가 tree[i]값을 부모로 한다는 의미이다.
  • tree[i]는 자식을 가진 노드라는 의미이므로 이 노드는 방문할 필요가 없다.
  • 만약 현재 노드가 지워지는 노드라면
    • 부모 노드가 리프노드가 될 수 있으므로, 부모 노드 추적을 하지 않는다.
  • boolean isLeafNode[] 에 리프 노드일 수도 있는 노드를 저장한다.

• isLeaftNode 값이 true인 노드만 DFS처리한다.

private static int dfs(int i)

i인덱스로부터 깊이우선 탐색을 실시한다.

• 현재 위치가 루트노드인 경우
  • 최초 호출한 i가 리프노드이므로 1을 반환한다.

• 현재 위치가 deleteNode인 경우
  • 제거되는 노드이므로 0을 반환한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class java_1068 {
    static int N;

    static int tree[];

    static int deleteNode;

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

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

        tree = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            tree[i] = Integer.parseInt(st.nextToken());
        }

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

        int result = solution();

        System.out.println(result);

        br.close();
    }

    private static int solution() {
        // 노드 전부를 돈다.
        // 만약 deleteNode를 만난다면 경로를 추가하지 않는다.
        // 중간 중간 방문하는 노드는 리프노드 false 처리 한다.
        // count 한다.

        // O(n^2)

        int result = 0;

        boolean isLeafNode[] = new boolean[N];
        Arrays.fill(isLeafNode, true);

        // 자식 노드를 가진 노드를 전부 false처리하자
        for (int i = 0; i < N; i++) {
            if (tree[i] == -1) {
                continue;
            }
            if (i == deleteNode) {
                continue;
            }
            isLeafNode[tree[i]] = false;
        }

        for (int i = 0; i < N; i++) {
            if (isLeafNode[i]) {
                result += dfs(i);
            }
        }

        return result;
    }

    private static int dfs(int i) {
        // 현재 위치가 루트인 경우 -> 1 반환
        if (i == -1) {
            return 1;
        }

        // 현재 위치가 deleteNode 인 경우
        if (i == deleteNode) {
            return 0;
        }

        return dfs(tree[i]);
    }
}

---

Uploaded by N2T