프로그래머스-길찾기 게임[Lv. 3] (C++)

프로그래머스

이진트리 노드의 모든 좌표 정보를 입력받을때 전위순회, 후위순회한 순서를 구하시오.

• 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
• 모든 노드는 서로 다른 x값을 가진다.
• 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
• 자식 노드의 y 값은 항상 부모 노드보다 작다.
• 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
• 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

 

풀이 방법

루트는 y가 가장 높은 노드입니다.
임의의 노드의 좌표 x값이 루트의 x값 보다 왼쪽에 있다면 무조건 왼쪽 서브트리입니다.
입의의 노드의 좌표 x값이 루트의 x값 보다 오른쪽에 있다면 무조건 오른쪽 서브트리 입니다.
 
즉, y를 기준으로 정렬 후, x값을 비교하여 왼쪽 서브트리에 넣을지, 오른쪽 서브트리에 넣을지 선택하면 됩니다.
루트의 왼쪽 서브트리로 넣으려는데 이미 왼쪽 자식노드가 설정되어 있다면 왼쪽 자식 노드의 자식 노드로 넣으면 되겠습니다.

void insert(Node &node)
{
    if (x > node.x)
    {
        if (left == nullptr)
            left = &node;
        else
            left->insert(node);
    }
    else
    {
        if (right == nullptr)
            right = &node;
        else
            right->insert(node);
    }
}

 

 

정답 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

struct Node
{
    int idx;
    int x;
    int y;
    Node* left;
    Node* right;
    
    bool operator < (Node& other)
    {
        if (y == other.y)
            return x < other.x;
        return y > other.y;
    }
    
    void insert(Node &node)
    {
        if (x > node.x)
        {
            if (left == nullptr)
                left = &node;
            else
                left->insert(node);
        }
        else
        {
            if (right == nullptr)
                right = &node;
            else
                right->insert(node);
        }
    }
    
    void Preorder(vector<int>& answer, int cnt = 1)
    {        
        answer.push_back(idx+1);
        
        if(left !=nullptr)
            left->Preorder(answer, cnt);
        
        if(right != nullptr)
            right->Preorder(answer, cnt);
    }
    
    void Postorder(vector<int>& answer)
    {
        if(left != nullptr)
            left->Postorder(answer);
        
        if(right != nullptr)
            right->Postorder(answer);
        
        answer.push_back(idx+1);
    }
};

Node 구조체
 

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    
    vector<Node> nodes;
    for (int i = 0; i < nodeinfo.size(); i++)
    {
        auto& node = nodeinfo[i];
        nodes.push_back(Node{i, node[0], node[1], nullptr, nullptr});
    }
    
    sort(nodes.begin(), nodes.end());

    Node root = nodes[0];
    
    for (int i = 1; i < nodes.size(); i++)
        root.insert(nodes[i]);
    
    vector<vector<int>> answer(2);
    root.Preorder(answer[0]);
    root.Postorder(answer[1]);
    
    return answer;
}