[백준](Java) 1068 - 트리

문제 링크

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

문제 풀이

굉장히 생각은 했지만 뭔가 정석풀이는 아니고 야매 풀이가 되어버린 느낌이다.
나중에 다른 사람들의 풀이를 다시 보고 참고할 예정
Node 클래스를 만들어서 해당 노드의 index를 알고, 그 노드의 상위노드, 그리고 하위 노드들을 저장할 수 있도록 했다.

    static class Node{
        int index;
        int prev;
        ArrayList<Integer> next;
        public Node(int index, int prev, ArrayList<Integer> next){
            this.index= index;
            this.prev = prev; //상위 노드
            this.next = next; //하위 노드
        }
        public String toString(){
            return "index : "+index +" || prev : "+prev+" || next : "+next.toString();
        }
    }

tree는 Node의 배열이며
Node의값중에 -1인 값부터 시작하기 때문에 이값을 startIdx 변수로 기억시킨다.
node들의 하위 노드는 input값을 다 받고, 상위노드로 자신을 가지는것들을 찾아서 추가했다.

        for(int i=0; i<n; i++){
           tree[i] = new Node(i,sc.nextInt(),new ArrayList<Integer>());
           if(tree[i].prev==-1){
               startIdx = i;
           }
        }
        k = sc.nextInt();
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(tree[i].index == tree[j].prev){
                    tree[i].next.add(tree[j].index);
                }
            }
        }

먼저 index가 k인 node를 삭제하는것이므로 chk[k]에서 true로 만들어서 후의 if조건을 통해서 걸러줘야지 생각했다.
만약에 삭제된 node가 root값일 경우 무조건 결과는 0이고 아닌경우 dfs를 돈다.

해당 index의 다음 node가 없을경우 자신이 마지막이므로 answer++
해당 node의 next값의 갯수만큼 for문을 도는데 여기서 next값중에 못가는 노드가 있는경우에 전체 다음 노드의 개수를 확인한다.
이때 노드의 갯수가 1개인 경우 그 노드가 없다면 자신이 마지막 노드라는 뜻이므로 answer++

코드

import java.util.*;

public class Main {

    static int n;
    static Node [] tree;
    static boolean [] chk;
    static Map<Integer,Integer> map = new HashMap<>();
    static int k;
    static int answer =0;

    static class Node{
        int index;
        int prev;
        ArrayList<Integer> next;
        public Node(int index, int prev, ArrayList<Integer> next){
            this.index= index;
            this.prev = prev; //상위 노드
            this.next = next; //하위 노드
        }
        public String toString(){
            return "index : "+index +" || prev : "+prev+" || next : "+next.toString();
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        tree = new Node[n];
        chk = new boolean[n];
        int startIdx = 0;
        for(int i=0; i<n; i++){
           tree[i] = new Node(i,sc.nextInt(),new ArrayList<Integer>());
           if(tree[i].prev==-1){
               startIdx = i;
           }
        }
        k = sc.nextInt();
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(tree[i].index == tree[j].prev){
                    tree[i].next.add(tree[j].index);
                }
            }
        }
        chk[k] = true;

        if(k==startIdx){
            System.out.println(0);
        }else{
            dfs(startIdx);
            System.out.println(answer==0 ? 1 : answer);
        }
    }

    public static void dfs(int idx){

        if(tree[idx].next.size()==0){// 자신이 마지막인지 체
            answer++;
            return;
        }

        for(int i=0; i<tree[idx].next.size(); i++){
            if(chk[tree[idx].next.get(i)]){
                if(tree[idx].next.size()==1){ //다음 node가 삭제된 상태에서, 자신이 마지막이 될것인지 체크하는 부분
                    answer++;
                }
                continue;
            }
            dfs(tree[idx].next.get(i));
        }

    }
}