[Baekjoon] 트리 - Java

문제

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

 

풀이

트리에서 한 개의 노드를 삭제했을 때, 리프노드의 수를 구하는 문제이다.

 

어떻게 하면 삭제처리를 하면서, 리프노드를 구할 수 있을까?

 

문제의 그림을 보면 삭제 노드의 자식 노드들을 모두 삭제처리를 해야하는 것을 보면 dfs를 사용해야겠다는 것을 자연스럽게 떠올릴 수 있다.

 

삭제 노드의 부모 노드가 삭제 노드만 자식으로 가지고 있었다면, 부모노드도 리프노드가 되어야한다.(이게 제일 중요하다)

즉 둘 사이을 끊어주는 것이 필요하다.

 

그래서 이 문제에서는 자식에서 부모를 가리키는 배열 + 부모에서 자식을 가리키는 배열 2가지가 필요하다.

 

1. 부모 자식간 연결 정보를 담는다.

 

2. 삭제 노드가 루트 노드일 경우, 모두 지워지므로 0을 출력하고 리턴한다.

 

3. 삭제 노드의 하위 노드를 모두 삭제 처리한다.

 

4. 삭제 되지 않았으면서, 자식 노드가 0개면 리프노드이므로 수를 센다.

 

소스코드

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

import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static ArrayList<Integer>[] graph;
    static boolean[] visited;

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

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

        graph = new ArrayList[n];
        int[] parent = new int[n];
        visited =  new boolean[n];

        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < n; i++) {
            int c = i;
            int p = Integer.parseInt(st.nextToken());

            parent[c] = p;

            if (p != -1) {
                graph[p].add(c);
            }
        }

        int removeNode = Integer.parseInt(br.readLine());

        if (parent[removeNode] == -1) {
            System.out.print(0);
            return;
        }

        for (int i = 0; i < graph[parent[removeNode]].size(); i++) {
            if (removeNode == graph[parent[removeNode]].get(i)) {
                graph[parent[removeNode]].remove(i);
            }
        }

        dfs(removeNode);

        int answer = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i] && graph[i].isEmpty()) {
                answer++;
            }
        }

        System.out.print(answer);

        br.close();
    }

    static void dfs(int node) {
        visited[node] = true;

        for (int next : graph[node]) {
            if (!visited[next]) {
                dfs(next);
            }
        }
    }
}

 

실행결과