[백준 2250] 트리의 높이와 너비 (C++)

2250번: 트리의 높이와 너비

 

이진 트리의 특성을 활용하는 문제

 

 

*주의 사항*

1. 트리의 루트 노드의 번호는 1이 아닐 수 있다.

2. 노드의 열의 위치는 이진 트리의 특성을 통해 결정된다.

 

1. dfs를 통해 트리를 탐색하며 각 노드별 왼쪽 자식 노드 수의 합, 오른쪽 자식 노드 수의 합을 구한다.
   
   
2. (1)과정을 통해서 각 노드별 자식 노드의 수를 알 수 있다. 자식 노드의 개수 + 1(현재 노드) 값이 N과 같으면 루트 노드임을 알 수 있다.
   
   
3. 각 노드별 좌, 우 노드 수를 구함과 동시에 깊이가 같은 노드들의 좌측 노드 수를 하나의 배열에 저장해둔다.
   - 여기서 노드별 좌, 우 노드 수란? 부모 자식에 상관없이 그림에서 보이듯 자신이 속한 열의 왼쪽, 오른쪽 노드의 수를 말한다.
   - 왜 필요한가? 좌, 우 노드 수를 알면 자신이 속한 열을 알 수 있다.
   - 왜 좌측 노드 수를 하나의 배열에 저장하는가? 좌측 노드 수를 알면 해당 노드가 속한 열의 번호를 알 수 있다.
   1. 노드별 좌, 우 노드 수를 구하기 위해 필요한 정보
      - 현재 노드가 부모 노드의 왼쪽 자식인지, 오른쪽 자식인지를 알아야 한다.
      - 현재 노드는 자신의 왼쪽, 오른쪽 자식 노드의 수를 알아야 한다. (1)과정에서 구할 수 있다.
      - 부모 노드의 좌측 노드 수, 우측 노드 수를 알아야 한다.
      
      그림을 보며 이해하면 편할 수 있어요.
   2. 현재 노드가 부모의 오른쪽인 경우 현재 노드의 좌측 노드 수 (5번 노드를 생각)
      -> 부모 노드의 왼쪽 노드 수 + 현재 노드의 좌측 자식 노드 수 + 1(부모 노드)
      
      
   3. 현재 노드가 부모의 오른쪽인 경우 현재 노드의 우측 노드 수 (5번 노드를 생각)
      -> 전체 노드의 수 - 현재 노드의 왼쪽 노드 수 - 1(자신)
      
      
   4. 현재 노드가 부모의 왼쪽인 경우도 동일하다.
      
      
4. 트리를 층별로 순회하며 해당 층에 있는 노드의 좌측 노드 수 배열(3번 과정에서 저장된)을 정렬한다.
   
   
5. 배열의 첫 번째 원소와 마지막 원소가 해당 층에서 가장 멀리 떨어진 두 노드가 된다.
   
   이 정도면 답을 구할 수 있을 것이다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>

typedef long long ll;
// typedef pair<int, int> pii;

using namespace std;


int N;
int tree[10001][2];
int childNodes[10001][2];
int leftNodes[10001]; // index
int rightNodes[10001];
bool visited[10001];

vector<int> levelNodes[10001];
pii answer = {1, 1};

void input(){
    cin >> N;
    int n, l, r;
    for(int i = 0; i < N; i++){
        cin >> n >> l >> r;
        tree[n][0] = (l != -1? l : -1);
        tree[n][1] = (r != -1? r : -1);
    }
}

int dfs(int now){
    if(now == -1) return 0;
    if(visited[now]) return childNodes[now][0] + childNodes[now][1] + 1;
    
    visited[now] = true;
    
    childNodes[now][0] += dfs(tree[now][0]);
    childNodes[now][1] += dfs(tree[now][1]);
    
    return childNodes[now][0] + childNodes[now][1] + 1;
    
}

void findSide(int now, int prev, bool flag, int depth){
    if(now == -1) return;
        
    // 현재 노드가 부모의 오른쪽
    if(flag){
        leftNodes[now] = leftNodes[prev] + childNodes[now][0] + 1;
        rightNodes[now] = N - leftNodes[now] - 1;
    }
    // 현재 노드가 부모의 왼쪽
    else{
        rightNodes[now] = rightNodes[prev] + childNodes[now][1] + 1;
        leftNodes[now] = N - rightNodes[now] - 1;
    }
    
    levelNodes[depth].push_back(leftNodes[now]+1);
    
    findSide(tree[now][0], now, false, depth+1);
    findSide(tree[now][1], now, true, depth+1);
}


void solve(){
    int root;
    
    for(int i = 1; i <= N; i++){
        if(visited[i]) continue;
        dfs(i);
    }
    for(int i = 1; i <= N; i++){
        if(childNodes[i][0] + childNodes[i][1] == N-1){
            root = i;
            break;
        }
    }
    
    leftNodes[root] = childNodes[root][0];
    rightNodes[root] = childNodes[root][1];
    levelNodes[1].push_back(leftNodes[root]+1);
    findSide(tree[root][0], root, false, 2);
    findSide(tree[root][1], root, true, 2);
    
    for(int d = 1; d <= N; d++){
        if(levelNodes[d].empty()) continue;
        if(levelNodes[d].size() == 1) continue;
        
        sort(levelNodes[d].begin(), levelNodes[d].end());
        int width = levelNodes[d].back() - levelNodes[d][0] + 1;
        if(answer.second < width) answer = {d, width};
    }
    
    cout << answer.first << " " << answer.second;
}

int main(){
    fastio
    input();
    solve();
    
    return 0;
}