[백준 java] 1068 - 트리

 

BFS를 사용하여 Leaf를 구하도록 구현하였다

 

주의할점은

1. 트리의 시작점은 여러개일 가능성도 있다 (여러개 트리)

2. 트리의 시작점은 꼭 0번째에 위치하지 않는다

 

둘째줄 0~N-1노드를 입력받을 때 입력값이 -1 이면 바로 큐에 담아주고 방문처리를 한다.

셋째줄 삭제할 노드를 입력받고 해당 노드를 가리키는 자식노드들을 

재귀함수를 통해 모두 삭제처리를 해주었다.

(직접 삭제가 아닌 삭제 노드에는 -2의 값을 주었다)

 

searchLeaf에서는 삭제된 노드 -2를 만나면 건너뛰고

방문하지 않은 자식노드를 찾으면 큐에 넣어준다. (해당 노드는 자식노드가 있으니 isLeaf는 false)

자식노드를 찾지못하면 Leaf 수를 ++ 해줘서 리프노드의 수를 구하였다

 

 

여러가지 반례

//ex1
4
-1 0 1 2
2
//output : 1

//ex2
7
3 6 6 -1 0 6 3
4
//output : 4

//ex3
7
-1 0 0 1 -1 4 4
3
//output : 4

//ex4
12
1 4 3 -1 3 1 2 0 6 6 6 1
2
//output : 3

---

트리문제만 나오면 꼭 하나씩 index에 값을 넣는다던가 실수를해서 틀리는것 같다...

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
// 트리
// https://www.acmicpc.net/problem/1068
public class B1068 {
    static int N;
    static int Leaf,Root = 0;
    static int[] Node;
    static Queue<Integer> q = new LinkedList<>();
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N =  Integer.parseInt(br.readLine());
        Node = new int[N];
        visited = new boolean[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        for(int i=0; i<N; i++){
            Node[i] =  Integer.parseInt(st.nextToken());
            if( Node[i] == -1 ){
                //시작점(-1)은 여러개일수도 있다
                q.add(i);
                visited[i] = true;
            }
        }
        int D = Integer.parseInt(br.readLine());

        deleteNode(D);
        searchLeaf();
        System.out.println(Leaf);
    }

    private static void deleteNode(int d) {
        Node[d] = -2;
        for(int i=0; i<N; i++){
            //해당 부모노드를 가리키는 자식노드들을 전부 -2로 바꿔준다
            if(Node[i]==d) deleteNode(i);
        }
    }

    private static void searchLeaf() {
        while(!q.isEmpty()){
            int temp = q.remove();
            boolean isLeaf = true;
            if(Node[temp] == -2) continue;
            for(int i=0; i<N; i++){
                if( !visited[i] && Node[i]==temp ){
                    visited[i] = true;
                    q.add(i);
                    isLeaf = false;
                }
            }
            if(isLeaf) Leaf++;
        }
    }
}