[1068] 트리

✔ 트리

[백준 1068]

문제 분석하기

리프 노드를 탐색하는 알고리즘을 수행할 때 제거하는 노드가 나온다면 탐색을 종료하도록 하는 아이디어로 접근

손으로 풀어보기

1. 인접 리스트로 트리 데이터를 구현
2. DFS 또는 BFS 탐색을 수행하면서 리프 노드의 개수를 셈
   • 단, 제거 대상 노드를 만났을 때는 그 아래 자식들과 관련된 탐색은 중지
   • 이는 제거한 노드의 점위에서 리프 노드를 제거하는 효과
3. 리프 노드의 개수를 출력

슈도코드 작성하기

N(노드 개수)
tree(트리 데이터 저장 인접 리스트)
visited(방문 기록 저장 배열)
answer(리프 노드 개수 저장 변수)
deleteNode(삭제 노드)
for(N의 개수만큼 반복하기) {
    tree 인접 리스트의 각 ArrayList 초기화하기
}
for(N개의 개수만큼 반복하기) {
    if(루트 노드가 아닌 경우)
        tree 인접 리스트에 트리 데이터 저장하기
    else
        루트 노드값 저장하기
}
삭제 노드값 저장하기
if(삭제 노드값이 0) 모두 삭제되므로 0을 출력하고 프로세스 끝냄
else DFS(root)
    answer 출력하기
    
DFS {
    visited 배열에 현재 노드 방문 기록하기
    if(현재 노드의 연결 노드 중 방문하지 않은 노드이고 삭제 노드가 아닐 때) {
        자식 노드 개수 증가
        DFS 실행하기(재귀 함수 형태)
    }
    만약 자식 노드 개수가 0이면 answer 변수 증가
}

코드 구현하기

/**
 * 1068) 트리
 */
public class D068_1068 {
    static ArrayList<Integer>[] tree;
    static boolean[] visited;
    // answer(리프 노드 개수 저장 변수)
    static int answer = 0;
    // deleteNode(삭제 노드)
    static int deleteNode = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(노드 개수)
        int N = sc.nextInt();
        // tree(트리 데이터 저장 인접 리스트)
        tree = new ArrayList[N];
        // visited(방문 기록 저장 배열)
        visited = new boolean[N];
        int root = 0;
        // tree 인접 리스트의 각 ArrayList 초기화하기
        for (int i = 0; i < tree.length; i++) {
            tree[i] = new ArrayList<>();
        }
        for (int i = 0; i < N; i++) {
            int p = sc.nextInt();
            // 루트 노드가 아닌 경우(부모 노드가 있다면)
            if (p != -1) {
                // tree 인접 리스트에 트리 데이터 저장하기
                tree[i].add(p);
                tree[p].add(i);
            }
            // 루트 노드값 저장하기
            else {
                root = i;
            }
        }
        // 삭제 노드값 저장하기
        deleteNode = sc.nextInt();
        // 삭제 노드값이 0 (루트를 삭제해야 한다면)
        if (deleteNode == root)
            // 모두 삭제되므로 0을 출력하고 프로세스 끝냄
            System.out.println(0);
        // DFS(root)
        else {
            DFS(root);
            // answer 출력하기
            System.out.println(answer);
        }
    }

    // DFS
    public static void DFS(int number) {
        // visited 배열에 현재 노드 방문 기록하기
        visited[number] = true;
        // cNode(자식 노드 개수)
        int cNode = 0;
        // 현재 노드의 연결 노드 중 방문하지 않은 노드이고 삭제 노드가 아닐 때
        for (int i : tree[number]) {
            if (visited[i] == false && i != deleteNode) {
                // 자식 노드 개수 증가
                cNode++;
                // DFS 실행하기(재귀 함수 형태)
                DFS(i);
            }
        }
        // 만약 자식 노드 개수가 0이면 answer 변수 증가
        if (cNode == 0)
            answer++;
    }
}