변경이력

돌아가기
2 879개 문자 추가 162개 문자 삭제

2016/11/30 03:03

Han Jooyung

## 아이디어 노드의 양팔 길이가 대칭이다. 재귀적으로 현재 노드에 대해 양쪽 자식이 모두 layout이 적용된 다음 컴팩트하게 자신의 팔 길이를 결정하면 된다. ### 양쪽 자식들의 팔길이 대칭 맞추기 우선 양쪽 자식은 따로 계산되므로 팔 길이가 깊이별로 달라질 수 있는데, 이를 먼저 맞춰줘야 한다. 예를 들어 왼쪽 자식은 팔길이가 최종 1-2-1으로 결정되었는데, 오른쪽 자식은 1-1-2로 결정되었다면 최종은 깊이별로 더 큰 값으로 맞춰서 1-2-2가 되어야 한다. ### 자신의 팔길이 결정하기 그런다음 컴팩트한 팔길이를 계산하려면 왼쪽 자식의 오른쪽 프로파일(단계별 가장 큰 x값들)과 오른쪽 자식의 왼쪽 프로파일(단계별 가장 작은 x값들)을 계산하여 각 단계별로 x가 겹치지 않는 팔길이를 계산하면 된다. ### 결정된 팔길이에 맞춰 양쪽 자식 떨어뜨리기 결정된 팔 길이에 맞춰서 다시 자식들을 translate하는 것도 필요. ## 코드 재귀를 위한 도움함수 `layout3`를 호출한다. 이때 기준 `x`는 마지막에 최소 `x` 기준점이 1이 되도록 translate해준다. 최소 `x`를 찾으려면 모든 노드를 탐색해야 한다. (오른쪽 자식의 왼쪽 자식이 최소 x를 가질 수도 있으므로) ```{.c} void tree_layout3(tree* t) { int height = tree_height(t) - 1; int* arms = (int*)calloc(height, sizeof(int)); layout3(t, 0, 1, arms, height); // arms 버퍼는 최종 결정된 팔길이를 저장한다. int minx = tree_leftmost(t)->x; // 최소 x가 1이 되도록 후보정 fold(t, INT_MAX, tree_xmin); tree_translate_x(t, 1-minx); free(arms); } ``` 재귀 `layout3` 함수는 먼저 왼쪽 오른쪽 자식을 처리한 다음 자식들이 겹치지 않도록 양쪽으로 벌려놓는다. 팔길이 대칭을 맞춰주기 위해 재귀계산을 할때 그 결과로 레벨별 팔길이를 반환한다.(`arms` 반환인자) ```{.c} void layout3(tree* t, int x, int y, int* arms, int n) { int* armsLeft = (int*)calloc(n-1, sizeof(int)); int* armsRight = (int*)calloc(n-1, sizeof(int)); t->x = x; // 여기서 굳이 x를 저장할 필요는 없다. 나중에 팔 길이가 결정된 다음 조정할 것이다. t->y = y; // 먼저 재귀적으로 팔 길이를 모두 결정한다. 이 때 x에서 시작하므로 겹칠 것이다. if (t->left) layout3(t->left, x, y+1, armsLeft, n-1); if (t->right) layout3(t->right, x, y+1, armsRight, n-1); // 단계별 팔 길이 중 큰 쪽으로 맞춰주기 for (int i=0; i<n-1; i++) { arms[i+1] = max(armsLeft[i], armsRight[i]); } if (t->left) layout3_setArms(t->left, x, arms+1); if (t->right) layout3_setArms(t->right, x, arms+1); // 여기부터 armsLeft와 armsRight는 그냥 버퍼로 사용 for (int i=0; i<n-1; i++) { armsLeft[i] = INT_MIN; armsRight[i] = INT_MAX; } // left의 오른쪽 프로파일 if (t->left) tree_right_profile(t->left, armsLeft); // right의 왼쪽 프로파일 if (t->right) tree_left_profile(t->right, armsRight); // 두 프로파일이 겹치지 않도록 현재 노드의 arm을 결정 int diff = INT_MAX; for (int i=0; i<n-1; i++) { if (armsRight[i] == INT_MAX || armsLeft[i] == INT_MIN) break; diff = min(diff, armsRight[i] - armsLeft[i]); } int arm = 1 + max(0, -diff / 2); // 왼쪽은 그대로 두고, 현재 노드와 오른쪽 자식을 translate t->x = x + if (t->left) tree_translate_x(t->left, -arm); if (t->right) tree_translate_x(t->right, arm * 2); arms[0] = arm; // 현재 노드 팔길이 저장 free(armsLeft); free(armsRight); } ``` 팔길이를 다시 맞추려면 ..재설정하는 함수 `setArms` ```{.c} void layout3_setArms(tree* t, int x, int* arms) { t->x = x; if (t->left) layout3_setArms(t->left, x-*arms, arms+1); if (t->right) layout3_setArms(t->right, x+*arms, arms+1); } ``` 왼쪽/오른쪽 프로파일 구하려면 모든 노드를 돌면서 x좌표의 min혹은 max를 저장하면 된다. `profile`은 레벨별로 최소값을 저장하기 위한 것이다. ```{.c} void tree_left_profile(tree* t, int* profile) { *profile = min(t->x, *profile); if (t->left) tree_left_profile(t->left, profile+1); if (t->right) tree_left_profile(t->right, profile+1); } void tree_right_profile(tree* t, int* profile) { *profile = max(t->x, *profile); if (t->left) tree_right_profile(t->left, profile+1); if (t->right) tree_right_profile(t->right, profile+1); } ``` 마지막으로 트리 전체의 최소 x는 right profile의 min값으로 계산할 수도 있겠으나 여기서는 `tree_fold` 라는 재귀함수를 이용하였다. ```{.c} int tree_xmin(tree* t, int l, int r) { return min(t->x, min(l, r)); } int tree_fold(tree* t, int z, int (*f)(tree*,int,int)) { if (!t) return z; int l = tree_fold(t->left, z, f); int r = tree_fold(t->right, z, f); return f(t, l, r); } ```
## 아이디어 노드의 양팔 길이가 대칭이다. 재귀적으로 현재 노드에 대해 양쪽 자식이 모두 layout이 적용된 다음 컴팩트하게 자신의 팔 길이를 결정하면 된다. ### 양쪽 자식들의 팔길이 대칭 맞추기 우선 양쪽 자식은 따로 계산되므로 팔 길이가 깊이별로 달라질 수 있는데, 이를 먼저 맞춰줘야 한다. 예를 들어 왼쪽 자식은 팔길이가 최종 1-2-1으로 결정되었는데, 오른쪽 자식은 1-1-2로 결정되었다면 최종은 깊이별로 더 큰 값으로 맞춰서 1-2-2가 되어야 한다. ### 자신의 팔길이 결정하기 그런다음 컴팩트한 팔길이를 계산하려면 왼쪽 자식의 오른쪽 프로파일(단계별 가장 큰 x값들)과 오른쪽 자식의 왼쪽 프로파일(단계별 가장 작은 x값들)을 계산하여 각 단계별로 x가 겹치지 않는 팔길이를 계산하면 된다. ### 결정된 팔길이에 맞춰 양쪽 자식 떨어뜨리기 결정된 팔 길이에 맞춰서 다시 자식들을 translate하는 것도 필요. ## 코드 재귀를 위한 도움함수 `layout3`를 호출한다. 이때 기준 `x`는 마지막에 최소 `x` 기준점이 1이 되도록 translate해준다. 최소 `x`를 찾으려면 모든 노드를 탐색해야 한다. (오른쪽 자식의 왼쪽 자식이 최소 x를 가질 수도 있으므로) ```{.c} void tree_layout3(tree* t) { int height = tree_height(t) - 1; int* arms = (int*)calloc(height, sizeof(int)); layout3(t, 0, 1, arms, height); // arms 버퍼는 최종 결정된 팔길이를 저장한다. int minx = tree_leftmost(t)->x; // 최소 x가 1이 되도록 후보정 fold(t, INT_MAX, tree_xmin); tree_translate_x(t, 1-minx); free(arms); } ``` 재귀 `layout3` 함수는 먼저 왼쪽 오른쪽 자식을 처리한 다음 자식들이 겹치지 않도록 양쪽으로 벌려놓는다. 팔길이 대칭을 맞춰주기 위해 재귀계산을 할때 그 결과로 레벨별 팔길이를 반환한다.(`arms` 반환인자) ```{.c} void layout3(tree* t, int x, int y, int* arms, int n) { int* armsLeft = (int*)calloc(n-1, sizeof(int)); int* armsRight = (int*)calloc(n-1, sizeof(int)); t->x = x; // 여기서 굳이 x를 저장할 필요는 없다. 나중에 팔 길이가 결정된 다음 조정할 것이다. t->y = y; // 먼저 재귀적으로 팔 길이를 모두 결정한다. 이 때 x에서 시작하므로 겹칠 것이다. if (t->left) layout3(t->left, x, y+1, armsLeft, n-1); if (t->right) layout3(t->right, x, y+1, armsRight, n-1); // 단계별 팔 길이 중 큰 쪽으로 맞춰주기 for (int i=0; i<n-1; i++) { arms[i+1] = max(armsLeft[i], armsRight[i]); } if (t->left) layout3_setArms(t->left, x, arms+1); if (t->right) layout3_setArms(t->right, x, arms+1); // 여기부터 armsLeft와 armsRight는 그냥 버퍼로 사용 for (int i=0; i<n-1; i++) { armsLeft[i] = INT_MIN; armsRight[i] = INT_MAX; } // left의 오른쪽 프로파일 if (t->left) tree_right_profile(t->left, armsLeft); // right의 왼쪽 프로파일 if (t->right) tree_left_profile(t->right, armsRight); // 두 프로파일이 겹치지 않도록 현재 노드의 arm을 결정 int diff = INT_MAX; for (int i=0; i<n-1; i++) { if (armsRight[i] == INT_MAX || armsLeft[i] == INT_MIN) break; diff = min(diff, armsRight[i] - armsLeft[i]); } int arm = 1 + max(0, -diff / 2); // 왼쪽은 그대로 두고, 현재 노드와 오른쪽 자식을 translate t->x = x + if (t->left) tree_translate_x(t->left, -arm); if (t->right) tree_translate_x(t->right, arm * 2); arms[0] = arm; // 현재 노드 팔길이 저장 free(armsLeft); free(armsRight); } ``` 팔길이를 다시 맞추려면 ..재설정하는 함수 `setArms` ```{.c} void layout3_setArms(tree* t, int x, int* arms) { t->x = x; if (t->left) layout3_setArms(t->left, x-*arms, arms+1); if (t->right) layout3_setArms(t->right, x+*arms, arms+1); } ``` 왼쪽/오른쪽 프로파일 구하려면 모든 노드를 돌면서 x좌표의 min혹은 max를 저장하면 된다. `profile`은 레벨별로 최소값을 저장하기 위한 것이다. ```{.c} void tree_left_profile(tree* t, int* profile) { *profile = min(t->x, *profile); if (t->left) tree_left_profile(t->left, profile+1); if (t->right) tree_left_profile(t->right, profile+1); } void tree_right_profile(tree* t, int* profile) { *profile = max(t->x, *profile); if (t->left) tree_right_profile(t->left, profile+1); if (t->right) tree_right_profile(t->right, profile+1); } ``` 마지막으로 트리 전체의 최소 x는 right profile의 min값으로 계산할 수도 있겠으나 여기서는 `tree_fold` 라는 재귀함수를 이용하였다. ```{.c} int tree_xmin(tree* t, int l, int r) { return min(t->x, min(l, r)); } int tree_fold(tree* t, int z, int (*f)(tree*,int,int)) { if (!t) return z; int l = tree_fold(t->left, z, f); int r = tree_fold(t->right, z, f); return f(t, l, r); } ```
1 Original

2016/11/16 03:08

Han Jooyung

코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.