DeveloperOC

🔗 문제

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

📌 문제 요약

입력: 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.
출력: 첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

💡 접근 방법

Tree 구조를 간단하게 구현하여 Root를 기준으로 각 순회에 맞게 출력시켜준다.

map과 pointer를 사용한 노드 구조 중 어느 것을 사용할 지 고민이 있었는데
최종적으로 map을 사용한 이유는 예제입력과 같이 입력 값을 받을 때
pointer를 사용하게 된다면 입력을 받은 후 연결을 따로 해줘야 하는 번거로움이 있기 때문이다.

map을 사용해 노드 이름을 key로 자식 노드들의 정보를 value로 저장 시킨다면,
자식 노드의 이름만 알고 있어도 해당 노드의 정보를 불러올 수 있게 된다.

⚠️ 처음에 했던 실수

전위 순회, 중위 순회, 후위 순회에 대한 개념 이해가 살짝 안되었다.

💻 코드

#include <iostream>
#include <map>
using namespace std;

class Node
{
public:
    char lChild;
    char rChild;
    char name;
};

int N;
map<char, Node> tree;

void PreOrder(char start)
{
    auto it = tree.find(start);

    if(it == tree.end())
        return;
    cout << start;
    PreOrder(it->second.lChild);
    PreOrder(it->second.rChild);
}

void InOrder(char start)
{
    auto it = tree.find(start);

    if(it == tree.end())
        return;
    InOrder(it->second.lChild);
    cout << start;
    InOrder(it->second.rChild);
}

void PostOrder(char start)
{
    auto it = tree.find(start);

    if(it == tree.end())
        return;
    PostOrder(it->second.lChild);
    PostOrder(it->second.rChild);
    cout << start;
}

int main()
{
    cin >> N;
    
    for(int i = 0; i < N; ++i)
    {
        Node* node = new Node();
        cin >> node->name >> node->lChild >> node->rChild;        
        tree.insert({node->name, *node});
    }

    PreOrder('A');
    cout << "\n";
    InOrder('A');
    cout << "\n";
    PostOrder('A');
    return 0;
}