[문제풀이] B1068 트리

트리

---

  🪅 parent배열을 보고 인접리스트를 구현할 수 있는가 (루트노드 지정)
  🪅 트리를 인접리스트로 구현할 수 있는가
  🪅 트리의 일부분을 잘라낼 수 있는가 => remove(int index)와 remove(Object obj)의 차이를 알고 있는가
  🪅 Leaf Node의 특징을 알고 있는가 => tree[node].size() == 0

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * 백준 1068번 트리
 * 입력:
 * 첫째 줄에 트리의 노드의 개수 N이 주어진다. 
 * N은 50보다 작거나 같은 자연수이다. 
 * 둘째 줄에는 0번 노드부터 N-1번 노드까지, 
 * 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 
 * 셋째 줄에는 지울 노드의 번호가 주어진다.
 * 
 * 출력:
 * 첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 
 * 리프 노드의 개수를 출력한다.
 */
public class Main {
    static List<Integer>[] tree;
    static int removeNode;
    static boolean[] isVisited;
    static int cnt;
    static int root;
    public static void DFS(int node) {
        if(node == removeNode) {
            isVisited[node] = true;
            return;
        }

        if(tree[node].size() == 0) {
            cnt++;
            return;
        }
        isVisited[node] = true;
        for(int adj : tree[node]) {
            if(isVisited[adj]) continue;
            isVisited[adj] = true;
            DFS(adj);
        }
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        tree = new ArrayList[N];
        // 각 배열 요소 ArrayList로 초기화
        for(int i = 0; i < N; i++) {
            tree[i] = new ArrayList<>();
        }

        isVisited = new boolean[N];
        StringTokenizer token = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++) {
            int parent = Integer.parseInt(token.nextToken());
            if(parent == -1) {
                root = i;
                continue;
            }
            tree[parent].add(i);
        }
        removeNode = Integer.parseInt(br.readLine());
        //test 출력
//        for(int i = 0; i < tree.length; i++) {
//            System.out.println(i + ": " + tree[i]);
//        }

        for(int i = 0; i < N; i++) {
            tree[i].remove(Integer.valueOf(removeNode));
        }

        DFS(root);
        System.out.println(cnt);
    }
}

💡 문제 접근 과정
지워진 부분트리를 제외하고 노드를 탐색(DFS)해서 말단노드(Leaf Node)의 개수를 찾는 문제이다.
처음에는 직접 지울 필요없이 지워야하는 노드에서 방문처리해서 그냥 넘기는 방식으로 풀었었다.
대부분의 케이스는 통과할 수 있었지만,
2
-1 0
1
이 입력으로 주어졌을 시(지우고 난후 루트 노드 하나만 남을때), 실패가 나왔다.
이 케이스까지 고려해서 다시 짜기보다는, 차라리 직접 지워야하는 노드만 실제로 지우자는 생각을 했다.
인접리스트에서 지워야하는 노드만 지우면 그 노드와 연결된 자식노드도 접근하지 못한다. (연결이 끊겨서)
트리를 순회하면서 해당노드가 발견되었을 시, List의 remove(Object obj)를 이용해서 해당 노드만 지웠고
root(입력마다 다름)부터 시작해서 DFS를 돌리고 말단노드에서 cnt ++해줘서 문제를 해결했다.