[백준] 1068번 - 트리 [Java]

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

 

[백준] 1068번 - 트리 [Java]

[백준] 1068번 - 트리 [Java]

---

1.  아이디어

 

트리의 루트부터 DFS 알고리즘으로 순회를 하며 리프 노드면 1을 반환하도록 구현했다.

---

2. 문제풀이

 

DFS 메서드에서 리프 노드인지 판단하는 boolean 변수를 활용해 자식 노드로 이동이 가능하면 리프 노드가 아니므로 자식 노드를 루트로 하는 트리에서 얻은 리프 노드의 수를 반환하고 자식 노드로 이동이 불가능하면 리프 노드이므로 1을 추가로 반환하도록 구현했다. 루트 노드 하나만 존재하는 트리도 리프 노드가 1개인 점에 주의해야했다.

---

3. 코드

 

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

public class Main {

    private static int N;
    private static int[] p;

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

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

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

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

        // 루트 노드를 삭제하는 경우
        if (root == target) {
            System.out.println(0);
            return;
        }

        int cnt = dfs(root, target);
        System.out.println(cnt);
    }

    private static int dfs(int node, int target) {
        int cnt = 0;
        boolean isLeaf = true;

        for (int next = 0; next < N; next++) {
            if (p[next] == node && next != target) {
                cnt += dfs(next, target);
                isLeaf = false;
            }
        }

        if (isLeaf) cnt++;

        return cnt;
    }

}

---

4. 후기