2250

백준 2250번

Link: 2250번: 트리의 높이와 너비

---

문제 설명

이번엔 DFS 문제다.

문제 보고나서 트리 그리는 규칙 이해하는데만 한참 걸린것 같다.

아무튼 이해하고 나서 트리를 직접 그려가면서 규칙을 찾아봤는데,

1. 우선 루트부터 찾은 다음 시작

2. 루트 기준으로 왼쪽 방향으로 DFS시 만나는 가장 마지막 노드가 트리의 가장 왼쪽 노드

3. 루트 기준으로 오른쪽 방향으로 DFS시 만나는 가장 마지막 노드가 트리의 가장 오른쪽 노드

4. 루트 왼쪽 자식에서 오른쪽으로 DFS시 만나는 가장 마지막 노드가 루트 바로 왼쪽 노드

5. 루트 오른쪽 자식에서 왼쪽으로 DFS시 만나는 가장 마지막 노드가 루트 바로 오른쪽 노드

이렇게 5가지 규칙을 찾았다.

이 규칙대로 트리를 만들고 문제를 풀어보려 했는데, 생각처럼 되지 않았다.

이 5가지 말고 내가 놓치고 있는 부분이 무엇인지 계속 생각해봤는데, 한가지 큰 부분을 놓치고 있었다.

이 트리를 그리는 규칙이 트리를 inorder 방식으로 탐색하는 순서와 같다는 점.

이 규칙 찾는데 하루는 더 걸린것 같다.

찾고 나니 푸는데 걸리는 시간은 순식간이었다.

트리의 각 노드들의 레벨만 구하면 되니까.

이 문제 알고리즘 분류가 DFS, 트리였는데 BFS를 넣어야 되지 않나 하는 생각도 들었다.

레벨 찾는데 사용한 알고리즘이 BFS였기 때문.

풀고 나니 나에게 실망스러웠는데, 그새 inorder, preorder, postorder 방식으로 트리 탐색하는 알고리즘을 까먹었다는 점 때문이다.

평소에 잘 알고 있었다면 트리 그리는 규칙 보자마자 아 이거 루트 찾아서 inorder로 탐색하면 끝나는 문제구나 했을텐데…

아무튼 늦게라도 떠올랐다는것 자체는 신기할 따름이다.

아직 갈길이 멀다는 생각밖에 안든다…

---

정답 코드

//
// Created by Keith_Lee on 21/02/2019.
//

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Node{
    int num = -1;
    int left = 0;
    int right = 0;
    int parent = -1;
    int level = -1;
    int location = 0;
};

int N;
int lastLevel = 0; // 트리 최대 레벨
int place = 1;

Node nodeTree[10001]; // 입력따라 트리 저장할 공간
bool visit[10001] = {false, };

void inOrder(int start){
    if(!visit[nodeTree[start].left]){
        inOrder(nodeTree[start].left);
    }

    nodeTree[start].location = place++;
    visit[start] = true;

    if(!visit[nodeTree[start].right]){
        inOrder(nodeTree[start].right);
    }
}

void BFS(Node start){ // 각 노드들의 레벨을 찾는다.
    int level = 1;
    queue<Node> Queue;
    vector<Node> nodes;

    Queue.push(start);

    while(!Queue.empty()){
        nodes.clear();

        while(!Queue.empty()){
            Node temp = Queue.front();
            Queue.pop();
            nodes.push_back(temp);
        }

        for(int i=0; i<nodes.size(); i++){
            Node current = nodes[i];
            nodeTree[current.num].level = level;

            if(current.left != -1){
                Queue.push(nodeTree[current.left]);
            }
            if(current.right != -1){
                Queue.push(nodeTree[current.right]);
            }
        }

        level++;
    }
}

int main(){
    visit[0] = true;
    cin >> N;

    int nodeNum;
    int leftChild;
    int rightChild;

    for(int i=1; i<=N; i++){
        cin >> nodeNum >> leftChild >> rightChild;

        nodeTree[nodeNum].num = nodeNum;
        if(leftChild == -1){
            nodeTree[nodeNum].left = 0;
        }
        else{
            nodeTree[nodeNum].left = leftChild;
            nodeTree[leftChild].parent = nodeNum;
        }

        if(rightChild == -1){
            nodeTree[nodeNum].right = 0;
        }
        else{
            nodeTree[nodeNum].right = rightChild;
            nodeTree[rightChild].parent = nodeNum;
        }
    }

    int root = 0;

    for(int i=1; i<=N; i++){
        if(nodeTree[i].parent == -1){
            root = nodeTree[i].num;
            break;
        }
    }

    BFS(nodeTree[root]); // 각 노드의 레벨을 지정한다.

    inOrder(root);

    for(int i=1; i<=N; i++){
        if(lastLevel < nodeTree[i].level){
            lastLevel = nodeTree[i].level;
        }
    }

    int maxWidth = 0;
    int maxLevel = 0;

    vector<int> levels;
    for(int i=1; i<=lastLevel; i++){
        levels.clear();

        for(int j=1; j<=N; j++){
            if(nodeTree[j].level == i){
                levels.push_back(nodeTree[j].location);
            }
        }

        sort(levels.begin(), levels.end());

        int width = levels[levels.size()-1] - levels[0] + 1;

        if(maxWidth < width){
            maxLevel = i;
            maxWidth = width;
        }
    }

    cout << maxLevel << ' ' << maxWidth << '\n';

    return 0;
}

---