[BOJ] 1068.트리.java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

문제 이해를 잘못하고 접근해서 엄청 틀렸다...

무튼 여차여차해서 부모 정보를 저장하는 배열과

자식 정보를 저장하는 ArrayList를 활용해서 풀었다.

코드 주석을 읽으면서 코드를 보면 이해가 쉬울 것이다!

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer;   public class BOJ1068 {       static int N, D, root, cnt = 0;     static int parents[];     static ArrayList<Integer> childs[];          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;                  N = Integer.parseInt(br.readLine());         parents = new int[N];    // 부모 정보를 저장하는 공간         childs = new ArrayList[N];    // 자식 정보를 저장하는 공간         for (int i = 0; i < N; i++)    // ArrayList 초기 설정             childs[i] = new ArrayList<Integer>();                  st = new StringTokenizer(br.readLine(), " ");         for (int i = 0; i < N; i++) {             int input = Integer.parseInt(st.nextToken());             // -1 을 입력받으면             if(input == -1) {                 // 루트 idx를 저장                 root = i;                 // 자기 자신이 부모                 parents[i] = i;             }             else {                 // 부모 노드의 정보 저장                 parents[i] = input;                 // 자식 노드들의 정보에 추가                 childs[input].add(i);             }         }           D = Integer.parseInt(br.readLine());         // root가 삭제되면 ByeBye~!         if(D == root) {             System.out.println(cnt);             return;         }         // 지울 노드를 저장하고있는 부모 노드로 가서, 지울 노드의 정보를 삭제         int delParent = parents[D];         for (int i = 0; i < childs[delParent].size(); i++) {             // 부모 노드에서 지울 노드 정보를 찾으면 지워주자             if(childs[delParent].get(i) == D) {                 childs[delParent].remove(i);                 break;             }         }         // 루트부터 리프 노드를 찾아보자.         find(root);                  System.out.println(cnt);     }          public static void find(int node) {         // 자식이 없으면 리프 노드         if(childs[node].size() == 0) {             cnt++;             return;         }         // 자식(의 자식의..) 노드들을 모두 탐색         for (int i = 0; i < childs[node].size(); i++)              find(childs[node].get(i));     }   }   Colored by Color Scripter

cs

#. Other Code