[ BOJ ] 2250번 : 트리의 높이와 너비

[ 오늘의 한줄평 ]
문제 제대로 읽어 빡대갈쓰야

에휴 쓰레기야.. 다음 N개의 줄에는 이걸 다음 N번째 줄 까지는 이라고 인식해버리는 나는 무엇일까? 2250번 채점 현황에 런타임 에러라는 족적을 누구보다 많이 남긴 사람이다 ^^V 슈밤

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

아 일단 진정하고....... 이번 문제에서 알아간 점이 있어서 적어본다........현타

---

2250번 : 트리의 높이와 너비

트리는 부모가 없다

처음에 틀렸습니다의 원인은 이거였다. 생각해보니까 처음부터 런타임 안난게 신기할 정도 문제를 꼼꼼히 읽지 않으면 망하는 케이스인데, 문제에서는 단 한번도 1번 노드가 루트 노드라고 말한적이 없다!!!!!!!!!

루트 노드를 찾아야 하는 셈이다. 주어지는 그래프는 이분 그래프라고 문제에서 명시를 해 주었기 때문에, 이분 그래프에서의 루트 노드는 부모가 없는 노드이다.

그건 알고 있었는데, 어떻게 찾지 하다가 질문 검색에서 천재를 만났다. 바로 1 ~ N 까지가 노드인데, 어떤 노드가 자식 노드일 경우 자식 노드라고 호출되는 경우는 딱 1번이므로 1부터 N까지의 합에서 자식 노드로 call된 노드 번호를 빼면 자식 노드로 언급되지 않은, 즉 부모가 없는, 다시 말해 루트 노드의 번호가 나온다. 유레카

int makeGraph(vector<child> &node, int V)
{
    int root = (V) * (V + 1) / 2;

    while (V--)
    {
        int n;
        cin >> n;
        cin >> node[n].leftChild >> node[n].rightChild;

        if(node[n].leftChild != -1)
            root -= node[n].leftChild;
        
        if(node[n].rightChild != -1)
            root -= node[n].rightChild;
    }

    return root;
}

문제 풀이

문제에서 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다. 부분에서 힌트를 얻어 inOrder를 이용하여 문제를 해결하였다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct child
{
    int leftChild = -1;
    int rightChild = -1;
};

int makeGraph(vector<child> &node, int V)
{
    int root = (V) * (V + 1) / 2;

    while (V--)
    {
        int n;
        cin >> n;
        cin >> node[n].leftChild >> node[n].rightChild;

        if(node[n].leftChild != -1)
            root -= node[n].leftChild;
        
        if(node[n].rightChild != -1)
            root -= node[n].rightChild;
    }

    return root;
}

int preOrder(vector<child> &node, vector<int> *level, int *column, int v, int lastcolumn, int lastLevel)
{
    int w = lastcolumn;
    level[lastLevel + 1].push_back(v);

    if (node[v].leftChild != -1)
        w = preOrder(node, level, column, node[v].leftChild, lastcolumn, lastLevel + 1);

    w = w + 1;
    column[v] = w;

    if (node[v].rightChild != -1)
        w = preOrder(node, level, column, node[v].rightChild, column[v], lastLevel + 1);

    return w;
}

void ans(vector<child> &node, vector<int> *level, int *column, int *width,int N, int root)
{
    preOrder(node, level, column, root, 0, 0);

    for (int i = 1; i <= N; i++)
    {
        if (level[i].size() != 0)
        {
            int max_column = column[level[i][0]];
            int min_column = column[level[i][0]];

            for (int j = 1; j < level[i].size(); j++)
            {
                if (column[level[i][j]] > max_column)
                    max_column = column[level[i][j]];
                else if (column[level[i][j]] < min_column)
                    min_column = column[level[i][j]];
            }
            width[i] = max_column - min_column + 1;
        }
        else
            width[i] = 0;
    }

    int maxWidthLevel = max_element(width, width + N + 1) - width;

    cout << maxWidthLevel << " " << width[maxWidthLevel];
}

int main()
{
    int N;
    cin >> N;

    vector<child> node(N + 1);
    vector<int> level[N + 1];
    int column[N + 1] = {0};
    int width[N + 1] = {0};

    int root = makeGraph(node, N);
    ans(node, level, column, width,N, root);
}