이번에 풀어본 문제는
백준 1068번 트리 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static List<List<Integer>> map;
    static int removeNode;
    static int answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        map = new ArrayList<>();
        for(int i = 0; i < N; i++) map.add(new ArrayList<>());

        StringTokenizer st = new StringTokenizer(br.readLine());

        int rootNode = 0;
        for(int i = 0; i < N; i++)
        {
            int next = Integer.parseInt(st.nextToken());
            //루트노드
            if(next < 0)
            {
                rootNode = i;
                continue;
            }
            map.get(next).add(i);
        }

        removeNode = Integer.parseInt(br.readLine());
        if(rootNode != removeNode)
        {
            remove(rootNode);
            if(map.get(rootNode).isEmpty()) answer = 1;
            else count(rootNode);
        }
        System.out.print(answer);
    }
    static void remove(int node)
    {
        Queue<Integer> q = new LinkedList<>();
        q.add(node);

        while(!q.isEmpty())
        {
            int n = q.poll();
            List<Integer> parent = map.get(n);
            int size = parent.size();
            for(int i = 0; i < size; i++)
            {
                int next = parent.get(i);
                if(next == removeNode)
                {
                    parent.remove(i);
                    break;
                }
                q.add(next);
            }
        }
    }
    static void count(int node)
    {
        for(int next : map.get(node))
        {
            if(map.get(next).isEmpty()) answer++;
            else count(next);
        }
    }
}

📝 풀이

주어진 트리에서 노드 하나를 삭제했을 때, 리프 노드의 개수를 출력하는 문제입니다.
먼저 삭제할 노드를 찾아야합니다. 해당 노드를 마주치자 마자 탐색을 종료하기 위해 bfs 탐색을 활용했고, 단방향 연결이기 때문에 삭제할 노드와 부모 노드와의 연결만 끊어주면 그 이후는 고려하지 않아도 됩니다.
remove함수로 노드를 제거해주었다면, 루트노드로부터 트리를 쭉 탐색하여 리프노드의 카운트를 올려주면 해결할 수 있습니다.

📜 후기

삭제연산 없이 하나의 함수로 해결하려고 했었는데, 코드가 복잡해져서 따로 분리했습니다. 이 풀이가 보기에도 더 깔끔한것같네요.