[백준] 1068번 : 트리

문제

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 중 하나를 제거할 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다.

둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다.

셋째 줄에는 지울 노드의 번호가 주어진다.

출력

첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

문제해결방법

각 노드의 부모가 주어졌을 때, 부모 노드에 자식 노드를 기록한다.

지울 노드는 부모 노드에 기록하지 않는다.

루트 노드부터 자식 노드들을 확인하며 리프 노드의 개수를 센다.

POINT

노드가 지워질 때 고려해야 할 3가지 경우

1. 지워지는 노드에 연결되어 있는 리프 노드

2. 지워지는 노드가 리프 노드인 경우

3. 노드가 지워져서 부모 노드가 리프 노드가 되는 경우

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main1068_트리 {
    public static int N;
    public static LinkedList<LinkedList<Integer>> node;
    public static int travel(int n) {
        if(node.get(n).size() == 0) return 1;
        int sum = 0;
        for(int i=0; i<node.get(n).size(); i++) {
            sum += travel(node.get(n).get(i));
        }
        return sum;
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        node = new LinkedList<>();
        for(int i=0; i<N; i++) node.add(new LinkedList<>());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int removeNode = Integer.parseInt(br.readLine());
        int root = -1;
        for(int i=0; i<N; i++) {
            int parent = Integer.parseInt(st.nextToken());
            if(parent == -1) root = i;
            else  {
                if(i != removeNode) node.get(parent).add(i);
            }
        }
        int leafNode = root!=removeNode?travel(root):0;
        System.out.println(leafNode);
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.