[백준]1068번 트리

1068번: 트리

(:30)

주어진 트리에서 노드 “하나”를 지웠을 때 남는 리프노드의 개수를 구하라

• 어떤 노드를 지우면 → 그 노드의 subtree까지 모두 제거된다.
• 노드의 개수는 최대 50
• 각 노드의 부모노드가 주어진다. ( 순서대로 주어짐. 즉 0번 노드의 부모노드, 1번노드의 부모노드... )
  • 만약 부모가 없다면(루트노드) -1이 주어진다.

문제 풀이

1. 최상위 root 노드를 기억 ( -1인 애 )
2. 최상위 루트 노드로부터 탐색하여 leaf노드의 개수를 구한다. ==> A개
   1. 어떻게?? → graph 라는 테이블을 두고, 여기에 각 노드의 부모노드값을 저장해 둔다.
   2. 재귀적으로 탐색할 때, graph[adj ] 가 cur인 노드로 traverse해 간다.
      • 따라서, 전체탐색을 해야함.. 그런데 문제에서는 n의 개수를 50개로 주어졌기 때문에 어떤 노드가 부모노드인지 탐색하는 과정은 총 50x50 이 일어나더라도 괜찮다.
   3. 만약, graph[adj ] 가 cur인 노드 가 없는 경우라면 ⇒ 현재 cur노드는 leaf 노드다
3. 제거하는 노드가 루트인 서브트리에서 leaf 노드의 개수를 구한다 . ==> B개
4. 제거노드(d)가 루트노드(r) 이 아닌 어떤 노드(p)의 자식노드였다면
   1. 제거 후, p가 leaf 노드가 되는 경우 → A+1
   2. 제거 후, p에는 남은 child가 있는 경우 → A는 변함없음
5. A-B를 한다.

• root노드를 제거하는 경우 → 즉시 0을 리턴

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;

    public static int r; // root node
    public static int d; // 제거 노드
    public static int n; // 노드의 개수
    public static int[] parent = new int[50]; // i 번 노드의 parent 노드

    public static void setting() throws IOException {
        n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i =0 ;i <n;i++){
            parent[i] = Integer.parseInt(st.nextToken());
            if(parent[i]==-1) r = i;
        }
        d = Integer.parseInt(br.readLine());
    }
    public static int solve(){

        // 제거 노드가 root노드인 경우
        if(d == r) return 0;

        int root = dfs(r); // 원래 트리의 leaf 노드 개수
        int sub = dfs(d);  // subTree의 leaf node 개수
        // 제거 노드가 root가 아닌 노드(p)의 자식노드였다면
        // 1. 제거 후 p가 leaf node가 되는 경우 : p의 자식노드가 없는 경우
        // 2. 제거 후 p의 자식 노드가 아직 하나 더 남아있는 경우 -> 변화없음.
        int p = parent[d];
        boolean flag = false;
        for(int i =0 ; i < n; i++){
            if(parent[i] == p && i != d) flag = true;
        }
        // 제거 후, p가 leaf 노드가 되는 경우
        if(!flag) root++;
        return root-sub;
    }
    public static int dfs(int cur){
        int sum = 0;
        boolean flag = false;
        // cur 을 parent 로 하는 자식노드가 존재 -> 해당 노드로 traverse 
        for(int i=0;i<n;i++){
            if(parent[i]!=cur) continue;
            sum += dfs(i);
            flag = true;
        }
        // child 가 없는 경우 -> 현재노드가 leaf노드다
        if(!flag) sum += 1;
        return sum;
    }

    public static void main(String[] args) throws IOException{
        setting();
        System.out.println(solve());

    }
}