[BOJ/백준] 2250 트리의 높이와 너비

● [문제번호 2250] 트리의 높이와 너비

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

2250번: 트리의 높이와 너비

 

● 알아야 할 것

: 이진트리

: 중위 순회

 

 

● 풀이 과정

: 생각보다 고려하여 구할 것이 꽤 있었다.

 

: 각 노드를 입력받고

왼쪽, 오른쪽 자식을 저장한 다음에

 

1. 이진트리의 Root 노드를 구하기

→ 모든 노드의 왼쪽, 오른쪽 자식에 없는 노드가 Root 노드이다.

 

2. 너비를 구할 때 사용할 '이진트리의 노드'의 index를 구한다.

→ 중위 순회를 통해 가장 왼쪽부터 오른쪽까지 순서대로 index를 구할 수 있다.

 

3. '각 레벨의 가장 왼쪽 자식'의 index 저장

 

4. '각 레벨의 가장 오른쪽 자식'의 index 저장

 

5. 저장한 index들을 계산하고 비교하여 가장 넓은 너비와 레벨을 구한다

 

 

● 주의 할 것

: 다 구현한 다음에 계속 3%에서 '틀렸습니다'를 받았는데

무엇이 문제인지 구글링하다가보니

문제의 지문에서 오해할만한 부분을 오해하고 있었다.

 

"트리의 레벨은 가장 위쪽에 있는 루트 노드가 1이고 아래로 1씩 증가한다."

라는 부분이다.

여기서 Root노드는 1이라고 이해하면 계속 틀리게 된다.

그래서 노드를 입력받고 Root노드를 구해야한다.

 

 

● 참고 할 것

: Root노드는 항상 1이 아니다.

http://melonicedlatte.com/algorithm/2018/08/26/193359.html

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// node[0] : "각 레벨의 가장 왼쪽 자식 노드"의 index 저장
// node[1] : "각 레벨의 가장 오른쪽 자식 노드"의 index 저장
// nodeIndex : 모든 노드의 index 저장
// lc, rc : 각 노드의 왼쪽 자식 오른쪽 자식 저장
// indexTemp : nodeIndex에서 index 저장할 때 사용
// depthLevel, depth : 가장 넓은 너비의 레벨과 너비 저장
// root : 이진트리의 root노드 저장
int node[2][10001];
int nodeIndex[10001];
int lc[10001], rc[10001];
int indexTemp = 1;
int depthLevel, depth = 0;
int N, root;

// 중위 순회로 node의 index를 저장한다
void inOrder(int p)
{
    if(lc[p] != -1)
        inOrder(lc[p]);
    
    nodeIndex[p] = indexTemp;
    
    indexTemp++;
    
    if(rc[p] != -1)
        inOrder(rc[p]);
}

// '각 레벨의 가장 왼쪽에 있는 노드'를 찾아서
// index를 저장한다
void leftOrder(int p, int level)
{
    if(!node[0][level])
        node[0][level] = nodeIndex[p];
    
    if(lc[p] != -1)
        leftOrder(lc[p], level + 1);
    
    if(rc[p] != -1)
        leftOrder(rc[p], level + 1);
}

// '각 레벨의 가장 오른쪽에 있는 노드'를 찾아서
// index를 저장한다
void rightOrder(int p, int level)
{
    if(!node[1][level])
        node[1][level] = nodeIndex[p];
    
    if(rc[p] != -1)
        rightOrder(rc[p], level + 1);
    
    if(lc[p] != -1)
        rightOrder(lc[p], level + 1);
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 노드의 lc, rc 저장
    for(int n = 0; n < N; n++)
    {
        int p, l, r;
        cin >> p >> l >> r;
        
        lc[p] = l;
        rc[p] = r;
    }
    
    // 1. root노드 구하기
    for(int parent = 1; parent <= N; parent++)
    {
        bool flag = true;
        
        // 모든 노드의 왼쪽 자식, 오른쪽 자식에 없는 노드가
        // 루트 노드이다
        for(int child = 1; child <= N; child++)
            if(lc[child] == parent || rc[child] == parent)
                flag = false;
        
        if(flag)
        {
            root = parent;
            break;
        }
    }
    
    // 2. 노드 index 저장
    // 3. '각 레벨의 가장 왼쪽 자식'의 index 저장
    // 4. '각 레벨의 가장 오른쪽 자식'의 index 저장
    inOrder(root);
    leftOrder(root, 1);
    rightOrder(root, 1);
    
    // 5. 가장 넓은 너비의 레벨과 너비 구하기
    for(int i = 1; i <= N; i++)
    {
        if(node[0][i] == 0 || node[1][i] == 0)
            break;
        
        int temp = node[1][i] - node[0][i] + 1;
        if(depth < temp)
        {
            depth = temp;
            depthLevel = i;
        }
    }
    
    // 출력
    cout << depthLevel << " " << depth;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [620 - 트리 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1991	트리 순회	https://pirateturtle.tistory.com/288
2	2250	트리의 높이와 너비	https://pirateturtle.tistory.com/289
3	11725	트리의 부모 찾기	https://pirateturtle.tistory.com/290
4	1167	트리의 지름	https://pirateturtle.tistory.com/291
5	1967	트리의 지름	https://pirateturtle.tistory.com/292