[백준 1068] 트리 (Java) - 트리, DFS

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

트리

문제

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

예를 들어, 다음과 같은 트리가 있다고 하자.

현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.

이제 리프 노드의 개수는 1개이다.

입력

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

출력

첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

예제 입력 1 복사

5
-1 0 0 1 1
2

예제 출력 1 복사

2

---

풀이

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

public class Main {
    static int N;
    static int[] parent;
    static int root, leaf, rid = 0;
    static boolean[] visited;
    static ArrayList<Integer>[] A;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 노드개수
        visited = new boolean[N];
        A = new ArrayList[N];

        // 인접리스트 초기화
        for(int i=0; i<N; i++){
            A[i] = new ArrayList<>();
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            int parentNode = Integer.parseInt(st.nextToken());
            if (parentNode == -1){
                root = i; // 부모노드가 -1이라면 해당 노드는 루트노드
                continue;
            }
            // 양방향 저장
            A[i].add(parentNode);
            A[parentNode].add(i);
        }

        rid = Integer.parseInt(br.readLine()); // 제거대상 노드번호

        // 제거대상이 루트노드라면 0 출력
        if (rid == root){
            System.out.println("0");
            return;
        }
        
        visited[rid] = true;
        DFS(root);
        System.out.println(leaf);
    }
    private static void DFS(int node){
        visited[node] = true; // 방문처리
        int count = 0;
        for(int now : A[node]){
            // node의 인접리스트 순회하면서 아직 방문하지 않은 노드있다면 DFS 재귀호출
            if (!visited[now]){
                DFS(now);
                count++;
            }
        }
        // 인접리스트를 순회했는데 DFS 재귀호출한 적이 없다면 leaf노드이다.
        if (count == 0) leaf++;
    }
}

• 트리, DFS를 활용한 문제
• 트리는 인접리스트 그래프 형태로 구현하였고, 연결정보를 일단 양방향으로 연결해주었다.
• 2번째 줄에서 만약 부모노드가 -1이라면 root라는 뜻이므로, root노드가 몇번 노드인지 따로 저장해주었다.
• 만약 제거대상 rid가 root노드라면 리프노드 자체는 존재하지 않게 된다.
  • rid == root 라면 "0"을 출력하고 함수를 종료시켜버린다.
• 애초에 제거대상 노드번호 rid를 방문처리를 먼저 해줘서, DFS 탐색할 일이 없게 했다.
• 그리고 root노드부터 DFS 탐색을 수행하였다.
• DFS
  • 파라미터로 받은 node번호에 대해서 방문처리를 해준다.
  • 그리고 DFS를 몇번 수행했는지 체크해주기 위해서 count 변수를 초기화 해준다.
  • node의 인접리스트를 순회한다.
    • 인접리스트 중 아직 방문하지 않은 노드가 있다면, DFS(now) 재귀호출 후,
    • 더 탐색할 노드가 있다는 뜻(= 리프노드 아님)이므로 count값을 증가시켜준다.
  • 인접리스트를 모두 순회한 후, count값이 0이라면 더이상 탐색할 노드가 없다는 뜻이다. 즉, 리프노드라는 뜻.
  • count == 0이라면 leaf++ 증가시켜준다.
• leaf의 개수를 출력해주면 된다.