[트리#4] 백준 1068번: 트리 JAVA

1068번: 트리

문제

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

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

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

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

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

 

 

입력

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

 

 

출력

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

 

 

예제입출력

 

 

풀이

 이번 문제는 입력받은 데이터를 기반으로 트리를 완성하고 -> 입력받은 특정 노드를 삭제 후 -> 트리의 리프 노드의 개수를 구하는 문제이다. 그냥 문제대로 알고리즘을 짜면 문제가 없을 것 같지만, 나는 예제입출력에서 첫번째 입력으로 -1을 받는 것을 보고 무조건 첫번째 입력값(0번 노드를 루트로)을 루트노드로 단정짓고 코드를 짜서 실패했다. 하지만 -1입력값은 2번째 3번째에 나타날 수 있다. 즉, 2번, 3번노드가 루트가 될 수도 있다는 것을 주의해야한다.

+ 추가적으로 루트노드를 제거할 경우 트리가 사라지므로 리프의 개수는 0개가 된다.(예외처리 추가)

 

• 노드의 삭제

위 그림과 같이 노드가 주어졌을 때 트리를 인접리스트로 구현하면 다음 표와 같은 형태를 띨 것이다.

인덱스[정점]	list[자식 노드 리스트]
0	[1, 2]
1	[3, 4]
2	[]
3	[]
4	[]

 여기서 1번 노드를 삭제하면 1번 노드에 연결되어 있는 3번, 4번노드가 삭제되어야 하는데 당연하고, 3번, 4번에 각각 자식노드들이 있다면 쭉 타고가서 다 삭제되어야 하는게 당연하다. 사람입장에서 생각하면 이게 당연하지만 컴퓨터는 다르다. 1번 노드에 3번과 4번 노드의 정보가 리스트로 저장되어 있고, 3번과 4번에도 자식노드가 있다면 리스트에 자식노드가 저장되어 있을 것이다. 

 하지만 트리의 탐색과정을 살펴보면 해당 개념을 적용할 수 있는데, 1번노드의 삭제가 주어지면 1번노드의 부모노드인 0번 노드의 자식노드 리스트에서 1번 노드만 삭제해주면 된다. 그러면 루트인 0번노드부터 탐색할 때 2번노드만 탐색하면 된다. 1번 노드에 3번 4번의 자식노드 리스트가 그대로 존재해도 문제가 되지 않는다. 따라서 이번 문제에서 parent[]배열로 각 노드의 부모노드 정보를 저장하여 사용하였다.

 

 

소스코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Tree4_1068 {

    static List<Integer>[] graph;
    static boolean[] visited;
    static int[] parent;
    static int count = 0;

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

        int n = Integer.parseInt(br.readLine());
        graph = new ArrayList[n];
        visited = new boolean[n];
        parent = new int[n];

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

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

            if (a == -1) {
                root = i;
            } else {
                graph[a].add(i);
            }
            parent[i] = a;
        }

        int d = Integer.parseInt(br.readLine());
        int pNode = parent[d];
        if(!(pNode == -1)){
            List list = graph[pNode];
            list.remove(Integer.valueOf(d));
            dfs(root);
        }else {
            count = 0;
        }

        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
    }

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

        if (graph[data].isEmpty()) {
            count++;
            return;
        }

        for (int i = 0; i < graph[data].size(); i++) {
            if (!visited[graph[data].get(i)]) {
                dfs(graph[data].get(i));
            }

        }
    }

}