문제

문제 링크

문제 접근

  • 이 문제는 트리의 중위 순회(inorder traverse)를 이용하면 각 노드의 열번호를 쉽게 발견할 수 있습니다.
  • traverse를 진행하면서 각 원소의 level을 찾아주고 각 level의 MAX와 MIN을 열번호를 통해 최신화 해줍니다.
  • par 값은 저장해서 root 노드를 찾는 용도로 사용합니다.
  • inorder traverse를 이용해서 차례대로 pos를 찾아주고 시켜주고 level의 MIN과 MAX를 통해 너비가 가장 넓은 위치를 찾아줍니다.

코드

#include <cstdio>
#include <vector>
#define pii pair<int, int>

using namespace std;

int max_lvl = 0, pos = 1, n, p, l, r, root = 1, par[10001], MIN[10001], MAX[10001];
vector<pii> v(10001);

void inorder(int root, int level){
    int left = v[root].first, right = v[root].second;
    if(level > max_lvl) max_lvl = level;
    if(left != -1)inorder(left, level + 1);
    if(MIN[level] > pos)MIN[level] = pos;
    if(MAX[level] < pos)MAX[level] = pos;
    pos ++;
    if(right != -1)inorder(right, level + 1);
}
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d %d %d", &p, &l, &r);
        v[p] = pii(l, r);
        par[l] = par[r] = p;
    }
    while(par[root] != 0)root = par[root];
    for(int i = 1; i <= 10000; i++) MIN[i] = 100000, MAX[i] = 1;
    inorder(root, 1);
    int ans = 1;
    for(int i = 1; i <= max_lvl; i++){
        if(MAX[i] - MIN[i] > MAX[ans] - MIN[ans])ans = i;
    }
    printf("%d %d", ans, MAX[ans] - MIN[ans] + 1);
}

느낀점

  • 트리의 순회를 풀면서 트리의 순회 방법에 대해 제대로 이해하게 된 것 같다.
  • 다음에 트리의 순회를 응용한 문제가 나오면 자신있게 풀 수 있을 것 같다^^