1R/2015 09 12

오늘의 문제

• 높이와 너비

참가자

• 15이원준

코드

15이원준

#include<iostream>
 
using namespace std;
 
int level[20000][2] = {0, };
int arr[20000][2];
int ex[20000][2] = { 0, };
int myNum[20000] = {0, };
int maxDep = 0;
int checkNum(int child){
  if(arr[child][0] != -1){
    ex[child][0] = checkNum(arr[child][0]);
  }
  if(arr[child][1] != -1){
    ex[child][1] = checkNum(arr[child][1]);
  }
  return ex[child][0] + ex[child][1] + 1;
}
void fill(int now){
  if(arr[now][0] != -1){
    myNum[arr[now][0]] = myNum[now] - ex[arr[now][0]][1] - 1;
    fill(arr[now][0]);
  }
  if(arr[now][1] != -1){
    myNum[arr[now][1]] = myNum[now] + ex[arr[now][1]][0] + 1;
    fill(arr[now][1]);
  }
}
void answer(int dep, int now){
  if(dep > maxDep){
    maxDep = dep;
  }
  if(arr[now][0] != -1){
    if(myNum[arr[now][0]] < level[dep][0]){
      level[dep][0] = myNum[arr[now][0]];
    }
    if(myNum[arr[now][0]] > level[dep][1]){
      level[dep][1] = myNum[arr[now][0]];
    }
    answer(dep + 1, arr[now][0]);
  }
  if(arr[now][1] != -1){
    if(myNum[arr[now][1]] < level[dep][0]){
      level[dep][0] = myNum[arr[now][1]];
    }
    if(myNum[arr[now][1]] > level[dep][1]){
      level[dep][1] = myNum[arr[now][1]];
    }
    answer(dep + 1, arr[now][1]);
  }
}
 
int main(){
  int N, root = -1;
  cin>>N;
  for(int i = 1; i<=N; i++){
    level[i][0] = N+1;
    level[i][1] = -1;
    ex[i][0] = 0;
    ex[i][1] = 0;
    int a;
    cin>> a;
    cin>> arr[a][0] >> arr[a][1];
    arr[arr[a][0]][0] = -1;
    arr[arr[a][0]][1] = -1;
    arr[arr[a][1]][0] = -1;
    arr[arr[a][1]][1] = -1;
    if(arr[a][0] == root || arr[a][1] == root || root == -1){
      root = a;
    }
  }
  ex[root][0] = checkNum(arr[root][0]);
  ex[root][1] = checkNum(arr[root][1]);
  myNum[root] = ex[root][0] + 1;
  fill(root);
  level[1][0] = myNum[root];
  level[1][1] = myNum[root];
  answer(2, root);
  int max = 0, bigLevel = 0;
  for(int i = 1; i<maxDep; i++){
    int tmp = level[i][1] - level[i][0] + 1;
    if(max < tmp){
      bigLevel = i;
      max = tmp;
    }
  }
  cout<< bigLevel << " " << max;
}

아이디어

15이원준

1. 루트를 찾으면 모든 입력을 저장한다.(arr에 저장)
2. 각각의 노드들의 왼쪽에 연결된 노드들의 수와 오른쪽에 연결된 노드들의 수를 구한다.(ex에 저장)
3. root노드의 열 넘버는 자신의 왼쪽에 연결된 노드들의 수 + 1 이다.(myNum에 저장)
4. 각 노드의 왼쪽노드의 열 넘버 = (자신의 열넘버) - (왼쪽노드의 오른쪽에 연결된 노드들의 수) - 1 이다. (myNum에 저장)
5. 각 노드의 오른쪽노드의 열 넘버 = (자신의 열넘버) + (오른쪽노드의 왼쪽에 연결된 노드들의 수) + 1 이다.(myNum에 저장)
6. 행에서 가장 왼쪽에 있는 노드의 열넘버와 가장 오른쪽에 있는 노드의 열넘버를 저장한다.(level에 저장)
7. 각 행의 너비를 구하고 가장 큰 값을 찾아 그 행의 번호와 너비를 출력한다.