1068 - 트리 (Java)

 

---

 

문제

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

 

 

풀이

처음 생각한 기본 컨셉은 예시만 보고,

 

루트 노드에서 시작해서 식별된 "리프 노드" 들에서

 

지울노드에서 탐색 후 식별된 "리프 노드" 를 빼주는것이었다.  (지울노드도 포함)

 

하지만 이 방법으로 했을시, 

 

1 - 2 - 3

 

과 같이 일직선 형태의 트리이고, (1이 root)

 

3를 지운다고 했을 때

 

루트노드에서 탐색시 리프노드는 1개이고,

지울노드인 3에서도 탐색시 리프노드는 1개이다.

 

이 때 리프노드의 개수를 빼주면 최종적으로는 리프 노드 개수가 0개가 되는데

 

실상은 1 - 2 와 같이 형태가 되며, 2라는 리프노드가 하나 존재하게 된다.

 

이후 생각을 조금 거쳐서 실제 노드들을 삭제할까 하다가,

그냥 플래그만 줘서 지우는 방식으로 분기처리를 하고 탐색시에 지움처리 되어있는

노드들은 방문하지 않는 방식으로 구현해서 풀이했다.

 

지울노드에서 탐색하면서 노드들을 지운 목록에 넣어준다.

이후 루트에서 탐색하면서, 지워지지 않는 노드들을 탐색 & 리프노드를 탐색한다.

 

최종적으로 리프노드의 개수를 구한다.

 

코드

import java.util.*;
import java.io.*;

public class Main {

    public static List<ArrayList<Integer>> tree = new ArrayList<>();
    public static List<Integer> removedNodes = new ArrayList<>();
    public static int rootNode = -1;
    public void solution() throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Integer numOfNodes = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Integer removeNode = Integer.parseInt(br.readLine());

        for (int i = 0; i < numOfNodes; i++) {
            tree.add(new ArrayList<>());
        }

        // 2 차원 리스트로 트리를 구성한다.
        for (int i = 0; i < numOfNodes; i++) {
            int node = Integer.parseInt(st.nextToken());
            // root node 일 경우
            if(node == -1) {
                rootNode = i;
                continue;
            }

            // 그 외의 노드일 경우 -> 부모에게 귀속된다.
            tree.get(node).add(i);
        }

        // 지울 노드들을 체크한다.
        removedNodes.add(removeNode);
        removeBfs(removeNode);
        System.out.println(bfs(rootNode));
    }

    public void removeBfs(int startNode) {
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(startNode);

        while(!queue.isEmpty()){
            int node = queue.pollFirst();

            // 자식의 개수를 체크한다. -> 자식 노드들이 지워진 노드에 없는지 체크한다.
            int numOfChild = tree.get(node).size();

            // 해당 tree 가 leaf 노드일때.
            if(numOfChild == 0) {
                removedNodes.add(node);
                continue;
            }

            for(int i=0; i<numOfChild; i++){
                queue.addLast(tree.get(node).get(i));
            }
        }
    }

    public int bfs(int startNode) {
        if(removedNodes.contains(rootNode)) return 0;

        int leafs = 0;
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(startNode);

        while(!queue.isEmpty()){
            int node = queue.pollFirst();
            List<Integer> existChild = new ArrayList<>();
            int numOfChild = 0;

            // 실질적인 자식의 개수를 체크한다. -> 자식 노드들이 지워진 노드에 없는지 체크한다.
            for(int i=0; i<tree.get(node).size(); i++){
                int childNode = tree.get(node).get(i);
                if(!removedNodes.contains(childNode)){
                    numOfChild++;
                    existChild.add(childNode);
                }
            }

            // 해당 tree 가 leaf 노드일때.
            if(numOfChild == 0) {
                leafs++;
            }

            for (Integer childNode : existChild) {
                queue.addLast(childNode);
            }
        }

        return leafs;
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

}

 

후기

 

더 깔끔한 방법이 있을거 같긴한데,, 생각나는대로