[백준/C++] 2250. 트리의 높이와 너비

문제

https://www.acmicpc.net/problem/2250

 

입력된 이진트리에 대해서 각 노드에 대해 세로위치(열)번호를 매겨서 가장 넓은 레벨을 찾고, 그 너비를 출력하는 문제이다.

풀이

left, rignt값을 가진 노드를 만들고, 노드번호가 0~N-1까지이기 때문에 N크기의 노드 배열을 만들어 트리로 이용했다. 

-> 루트를 알 수 없기 때문에, 입력받을 때 check배열에 자신,왼쪽자식,오른쪽자식 모두 +1을 했다. 

입력을 다 받은 후에 check[root] = 1이고 , root를 제외한 모든 노드는 2이다. 이렇게 루트를 찾았다. 

 

중위순회 : 왼->자신->오 순으로 방문 

따라서 트리를 중위순회하여 1부터 하나씩 증가시키며 열번호를 매겼다. 

이 때, level값을 이용하여 min_col[level], max_col[level]에 각각 해당 레벨의 최소 열번호, 최대 열번호를 저장했다.

* 이 탐색하는 부분에서 처음에 BFS랑 DFS개념 중에서만 풀이를 생각해서 굉장히 막막했다. 트리의 경우 세 가지 순회방식을 먼저 고려해보자..! 

 

마지막에는 min_col[level], max_col[level]를 돌면서, max_col[level] - min_col[level] 의 차이가 최소인 level을 찾았다. 

코드

#include <iostream>

using namespace std;
int N;

struct Node {
    int left;
    int right;
}Node;

// index 1~10000까지 이용할 것 
struct Node tree[10001];  
int check[10001] = {0,}; // 루트 찾기 위함
int min_col[10001];
int max_col[10001];

int col=1;
void inorderTraverse(int num, int level){ //중위 순회
    // 왼쪽 서브트리 
    if (tree[num].left > 0)
        inorderTraverse(tree[num].left, level+1);
    
    //중간 (자신)
    min_col[level] = min(min_col[level], col);
    max_col[level] = max(max_col[level], col);
    col++;

    //오른쪽 서브트리 
    if (tree[num].right > 0)
        inorderTraverse(tree[num].right, level+1);
}
int main(void){
    // input 처리
    cin >> N;
    for (int i=0;i<N;i++){
        int num, left, right;
        cin >> num >> left >> right;
        level[num]++;
        if (left != -1)
            level[left]++;
        if (right != -1)
            level[right]++;
        tree[num].left = left;
        tree[num].right = right;
    }
    //루트 찾기 
    int root;
    for (int i=1;i<=N;i++) {
        if (check[i] == 1)
            root = i;
    }

    fill(&min_col[0], &min_col[10001], 987654321); ///////
    fill(&max_col[0], &max_col[10001], 0);
    // 중위 순회 (열 번호 매기기)
    inorderTraverse(root, 1);

    //최대 너비와 해당 레벨 찾기 
    int result_level = 1;
    int result_width = max_col[1] - min_col[1] + 1; //// +1
    for (int i=2;i<=N;i++){
        int width = max_col[i] - min_col[i] + 1;
        if (result_width < width){
            result_level = i;
            result_width = width;
        }
    }
    cout << result_level << " " << result_width<< endl;
    return 0;
}

결과 

 

참고 

https://jaimemin.tistory.com/713