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

문제 링크입니다. https://www.acmicpc.net/problem/2250

2250번: 트리의 높이와 너비

중위 순회를 이용해 푸는 문제였습니다.

 

1부터 N까지 열이 존재할 때, 트리의 노드를 적정하게 배치하여 하나씩만 위치하게 합니다.

이때, 최대 길이를 가지는 행을 구해주면 되는 문제입니다.

 

이 문제를 트리를 탐색하는 3가지 방법 중에, 중위 순회 방법이 가장 적당합니다.

왜냐하면, 중위 순회는 왼쪽 자식 -> 부모 -> 오른쪽 자식의 순서로 탐색을 진행하는데 1번 값부터 채운다고 한다면,

가장 왼쪽 노드부터 채워나갈 수 있기 때문입니다.

다음과 같이 쉽고 정확하게 채울 수 있습니다.

 

단, 문제에서는 루트 노드가 존재하지 않기에 이를 찾아주셔야 합니다.

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
#define INF 987654321
using namespace std;

int N, root, node_place = 1; //처음의 위치는 1에서 시작한다
int low[10001]; // 같은 줄에서 가장 작은 위치
int high[10001]; // 같은 줄에서 가장 큰 위치
P Tree[10001]; // 부모와 자식을 저장
int Route[10001]; // 시작 루트를 찾는 배열

void dfs(int node, int cnt){
    if(Tree[node].F != -1){ //왼쪽 자식이 존재한다면, 왼쪽 자식을 먼저 탐색한다.
        dfs(Tree[node].F, cnt+1);
    }
    low[cnt] = min(low[cnt], node_place); // 현재 위치의 가장 작은 값
    high[cnt] = max(high[cnt], node_place); // 현재 위치의 가장 큰 값
    node_place++;
    if(Tree[node].S != -1){ // 마지막으로 오른쪽 자식을 탐색한다.
        dfs(Tree[node].S, cnt+1);
    }
}

void solve(){
    for(int i = 1; i <= N; i++){
        if(Route[i] == 1) root = i;
    }  
    dfs(root, 1);
    int ans = -1, level;
    for(int i = 1; i <= N; i++){
        int sum = high[i] - low[i] + 1;
        if(ans < sum){
            ans = sum;
            level = i;
        }
    }
    cout << level << " " << ans;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 0; i <= N; i++) low[i] = INF;
    for(int i = 1; i <= N; i++){
        int parent, child1, child2;
        cin >> parent >> child1 >> child2;
        Route[parent]++;
        if(child1 != -1) Route[child1]++;
        if(child2 != -1) Route[child2]++;
        Tree[parent] = {child1, child2};
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요