[백준] 1068번 : 트리

1068번: 트리

---

[DFS]

문제의 주어진 입력을 토대로 N x N 크기의 단방향 인접 행렬을 만들었다. 그리고 마지막 줄에서 제거할 노드의 번호를 입력 받는데, 이 때 제거할 노드를 방문 했다고 처리한다.

 

이제 DFS를 수행할 차례인데, 만약 root 노드와 제거할 노드가 동일하다면 DFS를 수행해서는 안된다. 따라서 root노드와 제거할 노드가 다르다면 DFS를 수행한다.

 

이때 DFS는 다음과 같은 로직을 갖는다.

    static void DFS(int x){

        visit[x] = true;
        boolean hasChild = false;

        for(int i=0; i<n; i++)
            if(mat[x][i] != 0 && !visit[i]) {
                hasChild = true;
                DFS(i);
            }

        if(!hasChild) cnt++;
    }

우선 x 노드를 방문하고, 자식 노드가 없다고 가정을 한다. 이후 인접 행렬을 돌며 자식 노드가 있다면 hasChild를 true로 변경해주고 DFS를 재귀호출한다. 만약 for루프를 돌았는데 자식노드가 없다고 판단되면 리프 노드라고 간주하고 개수를 증가시킨다.

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

public class Main {

    static boolean[] visit = new boolean[51];
    static int[][] mat = new int[51][51];
    static int n, cnt = 0;

    static void DFS(int x){

        visit[x] = true;
        boolean hasChild = false;

        for(int i=0; i<n; i++)
            if(mat[x][i] != 0 && !visit[i]) {
                hasChild = true;
                DFS(i);
            }

        if(!hasChild) cnt++;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int root = 0;
        n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            int val = Integer.parseInt(st.nextToken());

            if(val != -1)
                mat[val][i] = 1;
            else
                root = i;
        }
        int rm = Integer.parseInt(br.readLine());

        visit[rm] = true;
        if(root != rm)
            DFS(root);
        System.out.println(cnt);
    }
}