이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 74 번째 글 입니다.
목차
골드2 : 트리, 유니온파인드 문제이다.
Root 찾기
흠.. 입력으로 들어오는 node들이 순차적이지 않다는 점을 알아야 한다.이거 때매 시간 엄청 날렸다 즉, 랜덤으로 들어오는 그래프 정보를 가지고, 어떤 녀석이 tree의 root가 될 것인지 알아내야 한다. 이 과정에서 unionfind 방법을 사용한다. 트리의 자식은 부모를 따른다. 이 점을 사용하여 모든 자식이 따르는 부모을 적어둔 뒤, 최종적으로 갖는 부모가 무엇인지를 찾는다면, 해당 그래프의 root를 찾을 수 있다.
트리 그리기
그냥 보기에는 해당 문제는 헷갈린다.. 하지만 트리의 기본을 생각한다면 어렵지 않다. 트리는 전위탐색, 후위탐색, 중위(?)탐색이 있다. 용어보다는 의미가 중요하다.
위와 같은 트리가 있다고 할 때, 전위 탐색은 좌-중-우, 후위 탐색은 우-중-좌, 중위 탐색은 중-좌-우 와 같은 방식으로 탐색하는 방법이다.
이 점을 기억하고 있다면, 세가지 탐색 방법중 전위탐색을 위 문제에 적용해보자. 무조건 왼쪽 먼저 탐색한다면 오른쪽으로 가는 numbering을 하는데 있어 순차적이다.
물론 나는 처음에 각 node의 좌우 node 개수를 가지고 부모 노드의 위치를 결정하려 했으나, 이 방법이 보다 효과적이었다.
예외
문제는 10000개의 정보가 들어올 때 발생하는 트리의 크기를 잘 정해주어야 한다는 것이다. 나는 이 부분을 생각 못하고, 그냥 세그먼트 트리의 level을 구하는 것처럼 level = ceil(log2(N))+1 과 같이 두고 문제를 풀었는데, 당연히 컴파일 에러였다.멍청이
최악의 경우를 항상 생각해야 한다. 최악의 경우 10000개의 level을 가질 수 있으므로 이부분을 잘 고려해야 한다. 또한 이 정보를 저장하는 짓은 미친짓이다. 두번째 멍청이짓 10000*10000 배열이 너무 sparse 하다. 그러니, 문제에서 원하는 정보만 뽑아서 제출하는 것이 가장 좋다.
Code
#include <iostream>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
struct node {
int left;
int right;
};
int N;
int a[10010] = {0};
node b[10010] = {0};
vector<vector<int>> map;
int col = 1;
vector<pair<int, int>> width;
// Root 찾기
int find(int num){
if (num == a[num]) return num;
return a[num] = find(a[num]);
}
// Tree 채우며 정보 넣기
void fillTree(int num, int level){
if (num == -1) return;
fillTree(b[num].left, level+1);
map[level].push_back(col);
col++;
fillTree(b[num].right, level+1);
}
// 마지막 정답 찾는 과정에서 정렬 규칙
bool compare(pair<int, int> a, pair<int, int> b){
if (a.second == b.second) return a.first < b.first;
return a.second > b.second;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N;
vector<int> temp;
for (int i = 0; i <= N; i++) map.push_back(temp);
// unionfind를 위해 초기 부모를 자신으로 업데이트한다.
for (int i = 1; i <= N; i++) a[i] = i;
for (int i = 0; i < N; i++) {
int value, left, right;
cin >> value >> left >> right;
if (left != -1) a[left] = value;
if (right != -1) a[right] = value;
b[value].left = left;
b[value].right = right;
}
int root = find(1);
fillTree(root, 1);
pair<int, int> ans = {0,0};
for (int i = 1; i <= N; i++) {
int size = int(map[i].size());
if (size == 0) break;
sort(map[i].begin(), map[i].end());
int width = map[i][size-1]-map[i][0]+1;
if (ans.second < width) {
ans.first = i;
ans.second = width;
}
}
cout << ans.first << " " << ans.second << '\n';
return 0;
}