백준 1068 트리[JAVA]

🔗링크

1068 트리 Gold5

⚠️문제

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

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

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

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

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

입력

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

 

출력

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

🔍분석

---

처음 내용을 봤을 때, 개념이 유니온파인드랑 비슷한 느낌이 아닐까 싶어서, 비슷한 개념으로 구현해 보았다. 먼저 부모 노드를 입력받으면서 해당 부모의 자식 개수를 받는 배열을 선언하고 자식의 개수를 기록한다. 이렇게 하는 이유는 해당 노드가 리프노드인지 아닌지 체크를 해야하기 때문이다. 이후, 특정 노드가 지명되었을 때 해당 노드의 부모를 끊는다. 또한 부모를 끊었으니 해당 부모의 자식 수도 -1을 기록해준다. 

이제 모든 노드를 순회하면서, 리프노드인지 체크를하고 해당 노드의 최 상단 부모가 루트 노드라면  모든 조건에 부합하므로 결과값에 +1을 해주면 된다.

---

1. 변수 선언은 아래 코드와 같이 하였다. 부모노드를 기록하는 parent배열, 자식노드의 개수를 나타내는 haveChildNode배열을 선언하여 리프노드인지 체크하는데 활용할 것이다.

static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int[] parent;
static int[] haveChildNode;
static int N, removeNode, result = 0;

 

2. 다음은 부모노드를 기록하면서 부모노드의 자식의 개수를 카운트 해준다. 루트노드의 숫자 -1일 경우 배열초과가 나니 예외처리를 잘 해주어야한다.

for (int i = 0; i < N; i++) {
    int parentNode = Integer.parseInt(st.nextToken());

    parent[i] = parentNode;

    if (parentNode != -1) {
        haveChildNode[parentNode]++;
    }
}

 

3. 삭제할 노드를 입력받고, 해당 노드를 끊어 낼 것이니 해당 노드가 루트노드가 아니라면, 해당 노드의 부모가 가진 자식의 수를 1 감소시키고, 부모의 값에 의미없는 값 -2를 집어넣는다. 이후 모든 노드를 순회하며 리프노드 이면서 최상위 부모가 -1인 경우(최상위 노드가 루트노드, 만약 끊어낸 노드가 부모라면 -2를 반환할 것이다.)의 수가 해당 될 때, 결과 값을 증가시킨다.

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

if(parent[removeNode] >= 0){
    haveChildNode[parent[removeNode]]--;
}
parent[removeNode] = -2;

for (int i = 0; i < N; i++) {
    if(haveChildNode[i] == 0 && findParent(i) == -1){
        result++;
    }
}

4.부모를 찾는 로직이다. 재귀적으로 부모를 찾고 해당 최상위 부모가 -1이거나 -2일 경우(0보다 작을 경우) 해당 숫자를 반환한다. -1을 반환하는것은 루트노드가 정상적인 루트노드인 것이며, -2를 반환하는 경우는 루트노드가 끊어진 노드이므로 카운트 되지 않을 것이다.

public static int findParent(int node){
    if(node < 0){
        return node;
    }

    return findParent(parent[node]);
}

---

✔전체 코드

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[] parent;
    static int[] haveChildNode;
    static int N, removeNode, result = 0;

    public static void main(String[] args) throws IOException {

        N = Integer.parseInt(br.readLine());

        parent = new int[N];
        haveChildNode = new int[N];

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

        for (int i = 0; i < N; i++) {
            int parentNode = Integer.parseInt(st.nextToken());

            parent[i] = parentNode;

            if (parentNode != -1) {
                haveChildNode[parentNode]++;
            }
        }

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

        if(parent[removeNode] >= 0){
            haveChildNode[parent[removeNode]]--;
        }
        parent[removeNode] = -2;

        for (int i = 0; i < N; i++) {
            if(haveChildNode[i] == 0 && findParent(i) == -1){
                result++;
            }
        }

        System.out.println(result);
    }

    public static int findParent(int node){
        if(node < 0){
            return node;
        }

        return findParent(parent[node]);
    }
}

😄결과

초반에 루프 노드를 삭제할 때 삭제 노드의 부모노드도 리프노드가 될 수 있기에 자식 수를 감소시켜야 하는데 신경을 못써서 한 번 틀렸다. 그래도 직관적인 문제여서 빠르게 해결 했지만, 앞으로 꼼꼼하게 풀어야 한다고 느꼈다.