[1068번] 트리

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 트리에 대한 이해 :: http://www.crocus.co.kr/search/%ED%8A%B8%EB%A6%AC?page=3

2. Vector STL :: http://www.crocus.co.kr/500 , http://www.crocus.co.kr/501

트리라고 해서 왼쪽, 오른쪽 자식만 있다고 생각하면 큰 오산이란 걸 생각하고 시작해야 한다.

이진 트리라고 말하지 않았고, 사실 루트 노드도 몇개가 될 지 알 수 없다.(트리가 몇 개일지)

하지만 여기선 결과론적으로 트리는 1개만 있었고, 자식은 여러 노드가 존재할 수 있었다.

벡터를 이용하면 참 쉽게 해결할 수 있는 문제이다.

free(node)혹은 delete(node)같은 포인터를 이용하여 노드를 지우지 않고 

erase 벡터 함수를 이용하여 해결하면 빠르게 자식 노드를 지울 수 있고, 리프 노드로 만들 수 있다.

아이디어가 중요한 문제였기에 코드 설명은 주석 정도로만 남기려 한다.

소스 코드 : 

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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99

#include <iostream> #include <cstdio> #include <vector> #include <queue>   #define NODENUM 52   using namespace std;   typedef struct _TREE_ {     int val;     int parent;     vector<int> child;   }TREE;   queue<int> q; TREE tree[NODENUM];   int cnt;   void bfs(int start) {     q.push(start);       while (!q.empty())     {         int here = q.front();         q.pop();                  // 리프 노드이면         if (tree[here].child.empty())             cnt++;           for (int i = 0; i < tree[here].child.size(); i++)             q.push(tree[here].child[i]);     } }   int main() {     int n, start;       scanf("%d", &n);       for (int i = 0; i < n; i++)     {         scanf("%d", &tree[i].val);           if (tree[i].val == -1)         {             start = i;             continue;         }           else         {             int par = tree[i].val; // 부모             int chi = i; // 자식               tree[chi].parent = par;             tree[par].child.push_back(chi);         }       }       int del;       scanf("%d", &del);          // 예외적으로 루트 노드가 지워질 대상이면     if (del == start)     {         printf("0");         return 0;     }       // 해당하는 노드의 자식을 모두 지운다.     tree[del].child.clear();       // 해당하는 노드를 벡터에서 지운다.     int par = tree[del].parent;       for (int i = 0; i < tree[par].child.size(); i++)     {         if (tree[par].child[i] == del)             tree[par].child.erase(tree[par].child.begin() + i);     }              bfs(start);          printf("%d", cnt);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus