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

문제 링크

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

프로그래머스

 

 

코드 구현

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

using namespace std;

// 노드 정의
struct Node
{
    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;

private:
    // y가 큰 노드가 앞에, y가 같으면 x가 작은 노드가 앞에 오도록
    static bool CompareNodes(Node* a, Node* b)
    {
        if (a->y != b->y) return a->y > b->y;

        return a->x < b->x;
    }

    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;
    }

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

        // 부모 -> 왼쪽 -> 오른쪽
        path.push_back(node->id);
        PreOrder(node->left, path);
        PreOrder(node->right, path);
    }

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

        // 왼쪽 -> 오른쪽 -> 부모
        PostOrder(node->left, path);
        PostOrder(node->right, path);
        path.push_back(node->id);
    }


public:
    void BuildTree(const vector<vector<int>>& nodeinfo)
    {
        vector<Node*> nodes;

        for (int i = 0; i < nodeinfo.size(); ++i)
        {
            // 노드의 고유 숫자 = i + 1
            nodes.push_back(new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1]));
        }

        // 노드 정렬
        sort(nodes.begin(), nodes.end(), CompareNodes);

        // 이진 트리 구축
        for (Node* node : nodes)
        {
            root = AddNode(root, node);
        }
    }

public:
    vector<int> GetPreOrderPath()
    {
        vector<int> path;
        PreOrder(root, path);
        return path;
    }

    vector<int> GetPostOrderPath()
    {
        vector<int> path;
        PostOrder(root, path);
        return path;
    }


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

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

    BinaryTree tree;

    tree.BuildTree(nodeinfo);
    vector<int> pre = tree.GetPreOrderPath();
    vector<int> post = tree.GetPostOrderPath();
    
    return { pre, post };
}

 

 

해결 방법

이진 트리를 구현하기 위해 필요한 노드 구조체를 정의하고 트리 구현에 필요한 함수들을 BinaryTree 클래스 안에 선언하였다. 

• BuildTree 함수 : nodeinfo 안의 (인덱스, y, x) 값을 node 포인터 벡터에 전부 담아 y 값이 큰 노드가 앞으로 오도록, 만약 y 값이 같은 경우 x 값이 작은 노드가 앞으로 오도록 정렬한다. 정렬된 벡터의 모든 노드들에 대해 AddNode 함수를 실행하여 트리를 구축한다
• AddNode 함수 : 첫 번째 인자로 현재 추가하고자 하는 위치, 두 번째 노드로 추가할 노드를 넣어준다. 만약 현재 위치가 비어있으면 바로 노드를 넣어준다.
• PreOrder, PostOrder 함수 : 각각 전위순회(부모 -> 왼쪽 -> 오른쪽 자식), 후위순회(왼쪽 -> 오른쪽 -> 부모)를 수행한다