[백준] 1068 트리 - java

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

1068번: 트리

public class 트리 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Node tree[] = new Node[N];
        for (int i = 0; i < N; i++) {
            tree[i] = new Node();
        }

        int rootNode = 0;
        for (int i = 0; i < N; i++) {
            int value = Integer.parseInt(st.nextToken());
            if (value == -1) {
                rootNode = i;
            } else {
                tree[value].child.add(i);
            }

        }
        answer = 0;
        int removeNum = Integer.parseInt(br.readLine());
        if (rootNode == removeNum) {
            System.out.println(0);
        } else {
            removeDfs(rootNode, tree, removeNum);
            dfs(rootNode, tree, removeNum);
            System.out.println(answer);

        }
    }

    private static void removeDfs(int curNum, Node[] tree, int removeNum) {
        for (int i = 0; i < tree[curNum].child.size(); i++) {
            if (tree[curNum].child.get(i) == removeNum) {
                tree[curNum].child.remove(i);
                return;
            } else {
                removeDfs(tree[curNum].child.get(i), tree, removeNum);
            }
        }
    }

    static int answer;

    private static void dfs(int curNum, Node[] tree, int removeNum) {
        for (int i = 0; i < tree[curNum].child.size(); i++) {
            dfs(tree[curNum].child.get(i), tree, removeNum);
        }

        if (tree[curNum].child.isEmpty()) {
            answer++;
        }
    }

    static class Node {
        ArrayList<Integer> child = new ArrayList<Integer>();
    }
}

문제의 예시가 이진 트리여서 이진 트리 문제인줄 알았는데 트리였었다..

루트가 나중에 나오는 경우에 대해서 이해만 한다면 풀 수 있는 문제였다.

예를 들어 3 0 0 -1 1 의 경우

         3

      0    

   1   2

4

위의 그림과 같이 표현됩니다.

 

각 노드에 동적으로 자식을 담을 수 있는 ArrayList형식의 배열을 사용했습니다.

노드 삭제의 경우 루트의 위치에서 내려가면서 삭제 할 노드가 나오면 삭제했습니다.