BOJ) 트리 (1068 번)

트리

1068번: 트리

풀이

 

트리의 정보가 주어지고 특정 노드를 제거할 때, 리프노드가 몇 개 인지 찾는 문제다.

먼저, 트리의 각 노드는 하나의 부모를 가지고 있기 때문에 find-union을 사용해야겠다고 생각했다.

이전 find-union과 다른 점은 이미 부모에 대한 정보가 주어졌기 때문에, find할 때 더 상위 부모로 값을 최신화하지 않았다는 것이다. (최신화를 하게되면 루트 노드로 이어지기 때문에, 특정 노드를 제거했을 때, 자식노드를 제거할 수 없음)

 

다음으로는 입력받은 제거할 노드의 vertex를 받아서 parents를 수정해주었다.

해당 vertex의 parents를 임의로 제거됐다는 표시인 -2로 설정해주고, 이후 트리를 탐색하면서 지워지지 않은 노드를 찾았다.여기서, 자기 자신이 지워지지 않은 상태이며, 자신의 부모 노드가 지워지지 않았고, 자신은 자식 노드를 갖지 않는지 조건문을 통해 남은 리프노드를 찾았다.

 

 

~> 처음에는 Union을 사용해서 입력 받은 제거 노드를 부모로 갖는 노드들을 찾아 똑같이 표시를 해주려고 했지만, 오히려 불필요한 과정이라 느껴서 제외했다.

 

코드

 

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

public class Tree_1068 {
    static final int ROOT =-1, REMOVED =-2, ZERO =0, ADDITIONAL =1;
    static int[] parents;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        parents = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            parents[i] = Integer.parseInt(st.nextToken());
        }
        int removeNode = Integer.parseInt(br.readLine());

        br.close();
        solution(removeNode, n);
    }

    private static void solution(int removeNode, int n) {
        parents[removeNode] = REMOVED;
        int answer =0;

        for(int i=0; i<n; i++) {
            if(parents[i] != REMOVED) { // 자신이 루트가 아니고 지워지지 않은 경우
                answer += find(parents[i]) != REMOVED && !hasChildren(i) ? ADDITIONAL : ZERO;
            }
        }
        System.out.println(answer);
    }

    private static boolean hasChildren(int i) {
        for(int parentIdx : parents) {
            if(parentIdx == i) {
                return true;
            }
        }
        return false;
    }

    private static int find(int val) {
        if(val == REMOVED) {
            return val;
        } else if(val == ROOT) {
            return val;
        }
        return find(parents[val]);
    }
}