20190126 1068번 : 트리

트리

링크

풀이

• 트리를 만들고, 트리를 탐색하는 것에 대해 안다면 풀 수 있는 문제.
• 한 가지 유의할 점은 인풋으로 들어오는 데이터를 유심히 살펴봐야 할 것. 왜냐하면 부모노드가 이후에 나온다면 트리를 구성하는 시점에서 해당 노드는 트리의 구성요소가 되지 못한다. 따라서 두 가지 경우를 생각할 수 있다.
• 입력값을 받고 다시 재조정한다.
• 입력값을 받고 나서 이후에 자식에서 부모로 가는 방향의 노드는 생략한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static InputStreamReader isr;
    static BufferedReader br;
    static OutputStreamWriter osw;
    static BufferedWriter bw;
    static StringTokenizer st;
 
    static int count = 0;
    static Node root = null;
    
    public static void main(String[] args) throws IOException {
 
        isr = new InputStreamReader(System.in);
        br = new BufferedReader(isr);
        osw = new OutputStreamWriter(System.out);
        bw = new BufferedWriter(osw);
 
        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
 
        int rootNodeIndex = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        for(int i = 0; i < n; i++) {
            int parentNumber = Integer.parseInt(st.nextToken());
            
            if(parentNumber == -1) {
                rootNodeIndex = i;
                root = new Node(rootNodeIndex);
                continue;
            }
            
            map.put(i, parentNumber);
        }
        
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        for(int i = 0; i < n; i++) {
            list.add(new ArrayList<Integer>());
        }
        
        ArrayList<Order> orderList = setting(rootNodeIndex, list, map);
 
        /** 루트 노드를 제외한 나머지 노드들을 가지고 트리를 세팅한다. **/
        for(int i = 0; i < orderList.size(); i++) {
            Order order = orderList.get(i);
            searchAndAddNode(root, order);
        }
        
        /** 지울 노드의 번호를 선정한다. **/
        int removeNumber = Integer.parseInt(br.readLine());
        
        if(root.number != removeNumber) {
            removeNode(root, removeNumber);
            process(root);
        }
        
        bw.write(count + "\n");
        bw.flush();
        bw.close();
        br.close();
    }    
    
    private static ArrayList<Order> setting(int rootNodeIndex, ArrayList<ArrayList<Integer>> list, HashMap<Integer, Integer> map) {
        
        for(Integer childNumber : map.keySet()) {
            int parentNumber = map.get(childNumber);
            list.get(parentNumber).add(childNumber);
        }
        
        ArrayList<Order> orderList = new ArrayList<Order>();
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(rootNodeIndex);
        
        while(!queue.isEmpty()) {
            
            int rIndex = queue.poll();
            
            ArrayList<Integer> childList = list.get(rIndex);
            for(int i = 0; i < childList.size(); i++) {
                int childNumber = childList.get(i);
                orderList.add(new Order(childNumber, rIndex));
                queue.add(childNumber);
            }
        }
        
        return orderList;
    }
    
    /**
     * 루트노드 기반으로, order 를 추가하는 모듈 <br>
     * @param root
     * @param order
     */
    private static void searchAndAddNode(Node root, Order order) {
        
        /** 루트노드가 부모노드인 경우 **/
        if(root.number == order.parentNumber) {
            root.addNode(order.number);
            return;
        }
        
        /** 루트노드의 자식노드를 탐색 **/
        for(int i = 0; i < root.nodeList.size(); i++) {
            Node childNode = root.nodeList.get(i);
            searchAndAddNode(childNode, order);
        }
    }
    
    /**
     * 
     * @param root
     * @param removeNumber
     */
    private static void removeNode(Node root, int removeNumber) {
        
        boolean isFind = false;
        int findIndex = -1;
        
        for(int i = 0; i < root.nodeList.size(); i++) {
            Node childNode = root.nodeList.get(i);
            if(childNode.number == removeNumber) {
                isFind = true;
                findIndex = i;
                break;
            }
        }
        
        if(isFind) {
            root.nodeList.remove(findIndex);
            return;
        }
        
        for(int i = 0; i < root.nodeList.size(); i++) {
            Node childNode = root.nodeList.get(i);
            removeNode(childNode, removeNumber);
        }
    }
    
    private static void process(Node root) {
        
        if(root.nodeList.size() == 0) {
            count += 1;
            return;
        }
        
        for(int i = 0; i < root.nodeList.size(); i++) {
            Node childNode = root.nodeList.get(i);
            process(childNode);
        }
    }
}
 
/**
 * Order 객체
 * 
 * @field number : 현재 노드의 번호
 * @field parentNumber : 현재 노드의 부모 노드의 번호
 * @author PASUDO
 *
 */
class Order{
    int number; 
    int parentNumber;
    
    public Order(int number, int parentNumber) {
        this.number = number;
        this.parentNumber = parentNumber;
    }
}
 
/**
 * 자식 노드가 여러 개 일 수 있는 노드 클래스
 * @author PASUDO
 *
 */
class Node{
    int number = -1;
    ArrayList<Node> nodeList = null;
    
    public Node(int number) {
        this.number = number;
        this.nodeList = new ArrayList<Node>();
    }
    
    public void addNode(int paramNumber) {
        nodeList.add(new Node(paramNumber));
    }
}