[C++] Programmers Lv. 3 "길 찾기 게임"

🔵 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42892

프로그래머스

 

🔵 문제 의도

이진 트리를 직접 구현하여 전위, 후위 순회 값을 반환하는 것이다.

vector나 stack, queue를 직접 구현하듯이 이진 트리도 직접 구현하면 된다.

 

🔵 전체 코드

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

// 이진트리를 직접 구현하여 전위, 후위 순회하면 되는 문제
class Node
{
public:

    int id, x, y;
    Node* left = nullptr;
    Node* right = nullptr;

    Node(int id, int x, int y) : id(id), x(x), y(y) {}
};

class BinaryTree
{
private:
    Node* root = nullptr;

    static bool cmp(Node* a, Node* b)
    {
        if (a->y == b->y)
            return a->x < b->x;
        return a->y > b->y;
    }

    Node* AddNode(Node* current, Node* newNode)
    {
        if (current == nullptr)
            return newNode;

        if (newNode->x < current->x)
            current->left = AddNode(current->left, newNode);
        else
            current->right = AddNode(current->right, newNode);

        // (서브) 트리 루트 노드 반환
        return current;
    }

    // 전위 순회
    void PreOrder(Node* node, vector<int>& answer)
    {
        if (node == nullptr)
            return;

        answer.push_back(node->id);
        PreOrder(node->left, answer);
        PreOrder(node->right, answer);
    }

    // 후위 순회
    void PostOrder(Node* node, vector<int>& answer)
    {
        if (node == nullptr)
            return;

        PostOrder(node->left, answer);
        PostOrder(node->right, answer);
        answer.push_back(node->id);
    }

public:
    BinaryTree() : root(nullptr) {}

    void BuildTree(const vector<vector<int>>& nodeInfo)
    {
        vector<Node*> nodes;

        for (int i = 0; i < nodeInfo.size(); i++)
            nodes.push_back(new Node(i + 1, nodeInfo[i][0], nodeInfo[i][1]));

        sort(nodes.begin(), nodes.end(), cmp);

        for (Node* node : nodes)
            root = AddNode(root, node);
    }

    vector<int> GetPreOrder()
    {
        vector<int> ret;

        PreOrder(root, ret);

        return ret;
    }

    vector<int> GetPostOrder()
    {
        vector<int> ret;

        PostOrder(root, ret);

        return ret;
    }
};


vector<vector<int>> solution(vector<vector<int>> nodeinfo) 
{
    vector<vector<int>> answer;

    BinaryTree tree;
    tree.BuildTree(nodeinfo);

    vector<int> pre = tree.GetPreOrder();
    answer.push_back(pre);

    vector<int> post = tree.GetPostOrder();
    answer.push_back(post);

    return answer;
}

 

💡 헷갈렸던 부분

    Node* AddNode(Node* current, Node* newNode)
    {
        if (current == nullptr)
            return newNode;

        if (newNode->x < current->x)
            current->left = AddNode(current->left, newNode);
        else
            current->right = AddNode(current->right, newNode);

        // (서브) 트리 루트 노드 반환
        return current;
    }
    
    
    // 나중에 BuildTree에서 이렇게 호출한다
            for (Node* node : nodes)
            root = AddNode(root, node);

 

트리에 노드를 추가할 때  root = AddNode(root, node) 이런 식으로 진행하는데 처음에는 이해가 잘 안 갔다.

AddNode에서 return current 할 때 반환하는 것이 서브 트리 혹은 트리의 root라는 것을 명심하자.

노드를 새로 추가할 때만 새로운 노드를 상위 재귀에 반환하고, 그 이후는 서브 트리 혹은 트리의 root를 반환하는 것이다.

따라서 자연스럽게 트리가 연결된다.

 

🔵 시간 복잡도

시간 복잡도에 가장 영향을 미치는 부분은 트리 빌드의 마지막 for(AddNode하는 부분)이다.

입력으로 주어지는 nodeInfo의 크기를 N이라 하자.

AddNode에서 트리가 균형 상태일 경우 O(logN), 편향 상태일 경우 O(N) 시간 복잡도를 가진다.

따라서 최악의 경우, 시간 복잡도는 O(N^2)이다.