백준 12767 Ceiling Function

문제 URL : https://www.acmicpc.net/problem/12767

12767번: Ceiling Function

 

문제접근법 : BST를 직접구현한후 0~n-1번 bst를 생성합니다. 

그리고 0~n-1번까지 같은모양의 트리가 있는지 찾아 같은모양끼리 같은 색상으로 색칠해줍니다.

아래 사진처럼

같은 모양끼리 색칠하기

 

색칠되있는것은 굳이 또 찾을필요 없고 색칠되있지 않는 모양끼리 탐색만해주고 

몇가지가 색칠되있는지 값을 구해주면 되는문제이기에 문제는 어렵지 않습니다.

시간복잡도는 n^2 * k이기때문에 쉽게 구현이 가능하나 조금만더 생각하면 n^2안에도 풀수있을듯한데 귀찮아서 

그냥 풀었습니다.

 

소스코드 : 

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 100 101 102 103 104 105 106 107 108 109

//By콩순이냉장고 #include <bits/stdc++.h> using namespace std;   struct Node {     int data;     Node* left = NULL, * right = NULL;   }; struct binarytree {     Node* root = NULL;     void insert(int data) {           if (root == NULL) {             root = new Node;             root->data = data;             return;         }         Node* cur = root;         Node* before = cur;         while (cur) {             before = cur;             if (cur->data > data)                 cur = cur->left;             else                 cur = cur->right;         }         cur = new Node;         cur->data = data;         if (before->data > data)             before->left = cur;         else             before->right = cur;     } };   int n, k; binarytree tree[50]; void input() {     cin >> n >> k;     int t;     for (int i = 0; i < n; i++) {         for (int j = 0; j < k; j++) {             cin >> t;             tree[i].insert(t);         }     } } int child(Node* a) { //자신을 기준으로 자식이 어떻게있는지 왼쪽이있거나 혹은 오른쪽이있거나 혹은 둘다 혹은 아예없거나     int t = 0;     if (a->left)         t |= 1 << 1;     if (a->right)         t |= 1 << 2;     return t; }   bool sameshape(Node* a, Node* b) {     return child(a) == child(b); } bool issame(Node* a, Node* b) {     bool flag = sameshape(a, b); //루트부터 자식모양이 같은지 다르면 바로 다른거니 false겠지만 같으면 같은모양인지 계속 확인해나감     if (flag) {         if (a->left)             flag = flag && issame(a->left, b->left);         if (a->right)             flag = flag && issame(a->right, b->right);     }     return flag; }   void solve() {       int color[50] = { 0 };     memset(color, -1, sizeof(color));     int visit[50] = { 0 };     for (int i = 0; i < n; i++) {         if (color[i] > -1)             continue;         color[i] = i; //색상을입힘         for (int j = i + 1; j < n; j++) {             if (color[j] > -1)                 continue;             if (issame(tree[i].root, tree[j].root))                 color[j] = i;         }     }     int res = 0;     //몇가지의 색상이있는지     for (int i = 0; i < n; i++) {         visit[color[i]] = 1;     }     for (int i = 0; i < n; i++)         res += visit[i];     cout << res << "\n";     }     int main() {     ios::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     //freopen("input.txt", "r", stdin);     input();     solve(); } Colored by Color Scripter

cs

 

 

궁금한점혹은 모르는점 혹은 논리적인오류 어떤 질문이든 괜찮으니 댓글은 언제나 환영입니다.