백준 1068

문제 1068번

짤린부분 = https://www.acmicpc.net/problem/1068

소스코드

import java.io.*;
import java.util.*;
public class boj1068 {
    static int N;
    static List<Integer>[] list;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        list = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            list[i] = new ArrayList<>();
        }
        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = -1;
        for (int i = 0; i < N; i++) {
            int input = Integer.parseInt(st.nextToken());
            if(input == -1){
                start = i;
                continue;
            }
            list[input].add(i);
        }
        int remove = Integer.parseInt(br.readLine());
        remove(remove);
        if(remove == start){
            System.out.println(0);
        }else{
            Stack<Integer> stack = new Stack();
            stack.add(start);
            int cnt = 0;
            while(!stack.isEmpty()){
                int a = stack.pop();
                if(list[a].size() == 0){
                    cnt++;
                    continue;
                }
                for (int i = 0; i < list[a].size(); i++) {
                    stack.add(list[a].get(i));
                }
            }
            System.out.println(cnt);
        }
    }
    public static void remove(int remove){
        if(list[remove].size() >0){
            int size = list[remove].size();
            while(size>0){
                int child = list[remove].get(--size);
                remove(child);
            }
        }
        for (int i = 0; i < N; i++) {
            if(list[i].contains(remove)){
                for (int j = 0; j < list[i].size(); j++) {
                    if(list[i].get(j) == remove){
                        list[i].remove(j);
                    }
                }
            }
        }
    }
}

풀이 접근

1. 트리 자료구조에 대해서 이해한다.
2. 몇 번째 노드가 자식 노드를 얼마나 가지고 있는지를 표현하기 위해서 2차원 리스트를 만든다. (트리 구조를 만들기 위함)
3. 반복문을 통해서 트리 구조를 완성한다.
4. remove 재귀함수를 통해서 제거할 노드를 제거한다.
5. 자식 노드가 없는 노드를 구하기 위해서 스택을 생성하고, 시작점이 되는 값을 넣어준다.
6. 반복문을 통해서 자식노드가 없는 노드를 만날 경우에만 카운트를 해주고, 마무리로 출력한다.

문제 핵심

• 자료구조의 이해도
• 2차원 list를 활용할 수 있는지