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

길 찾기 게임(Level 3)

문제

전체 문제 보기

코딩테스트 연습 - 길 찾기 게임

접근법

이번 문제는 주어진 노드들의 정보를 활용하여 이진트리를 만들고, 만들어진 이진트리를 활용하여 전위 순회와 후위 순회를 한 결과를 배열에 저장하는 문제입니다. 이진트리를 만들기 위해서는 부모 노드 → 자식 노드 순으로 트리에 삽입할 경우 구현의 복잡도를 많이 줄일 수 있습니다. 그래서 주어진 nodeinfo를 다음과 같이 y값을 기준으로 정렬 후 Tree에 삽입하였습니다. Tree 구현에 대한 설명은 아래에서 계속 진행하겠습니다.

    auto comp = [](const vector<int>& lhs, const vector<int>& rhs)
    {
        if(lhs[1] > rhs[1]) return true;
        else if(lhs[1] == rhs[1] && lhs[0] < rhs[0]) return true;
        else return false;
    };
    sort(nodeinfo.begin(), nodeinfo.end(), comp);

Tree 구현

Node 구조체

먼저 Node 구조체는 다음과 같습니다.

struct Node{
    Node(int _n, int _x, int _y) : num(_n), x(_x), y(_y) {}
    Node* left{};
    Node* right{};
    int num;
    int x;
    int y;
};

각 노드는 왼쪽 자식과 오른쪽 자식을 가질 수 있고, 자신의 번호와 위치정보를 생성시 입력받습니다.

Tree class

class Tree{
public:
    Tree(int n, int x, int y); 
    void AddNode(int n, int x, int y);
    void AddAnswerPostOrder(vector<vector<int>>& answer);
    void AddAnswerPreOrder(vector<vector<int>>& answer);
    ~Tree();
private:
    Node* root;
    void Recursive_addNode(Node* root, Node* newNode);
    void Recursive_PostOrder(Node* root, function<void(Node* node)> func);    
    void Recursive_PreOrder(Node* root, function<void(Node* node)> func);
};

Tree 객체는 root 노드를 가집니다. 처음 Tree를 생성할 때 root 노드의 정보를 입력받습니다. 이후 노드를 추가할 수 있는 AddNode 멤버함수와 후위 탐색, 전위 탐색 결과를 Answer 배열에 추가하는 AddAnswerPostOrder 멤버 함수, AddAnswerPreOrder 멤버 함수를 제공합니다. 그리고 노드를 동적 할당하여 사용하기 때문에 소멸자에서 동적 할당한 노드를 모두 제거해야 합니다.

 

Tree 클래스에서 제공하는 4개의 public 멤버 함수 모두 내부적으로는 재귀적 호출을 통해서 구현하였습니다. 이때 사용할 재귀 함수를 private으로 선언하였습니다.

Node 추가

Tree에서 노드를 추가하기 위해서 AddNode 함수를 제공하고 있습니다. 인자로는 노드 번호n, 노드 위치(x,y)를 받고 있습니다. AddNode 함수에서는 노드를 동적할당 한 후, Recursive_addNode 함수를 통해서 재귀적으로 노드위치를 찾아가도록 구현하였습니다.

void Tree::AddNode(int n, int x, int y)
{
    Node* newNode = new Node(n,x,y);
    Recursive_addNode(root, newNode);
}
void Tree::Recursive_addNode(Node* root, Node* newNode)
{
    if(root->x > newNode->x)
    {
        if(root->left == nullptr)
            root->left = newNode;
        else
            Recursive_addNode(root->left, newNode);
    }
    else
    {
        if(root->right == nullptr)
            root->right = newNode;
        else
            Recursive_addNode(root->right, newNode);
    }
}

후위 순회, 전위 순회

Recursive_PostOrder, Recursive_PreOrder 멤버 함수는 함수를 인자로 받는 고차함수(high order function)입니다. Recursive_PostOrder, Recursive_PreOrder 함수는 방문 시 수행할 함수를 인자로 받습니다. 그래서 AddAnswerPostOrder에서는 Recursive_PostOrder를 통해서 answer 배열에 결과를 추가하는 기능으로 활용하고, 소멸자에서는 node를 제거하는 기능으로 사용하여 코드의 재사용성을 높였습니다. 활용법은 다음과 같습니다.

Tree::~Tree()
{
    auto deleteNode = [](Node* node)
    {
        delete node;
    };
    Recursive_PostOrder(root, deleteNode); // 후위 순회를 하며 모든 노드를 제거한다.
}
void Tree::AddAnswerPostOrder(vector<vector<int>>& answer)
{
    auto AddAnswer = [&answer](Node* node)
    {
        answer[1].push_back(node->num);
    };
    Recursive_PostOrder(root, AddAnswer); // 후위 순회를 하며 모든 노드를 answer 배열에 담는다.
}

Recursive_PostOrder, Recursive_PreOrder 멤버함수는 다음과 같이 구현할 수 있습니다.

// 후위 순회
void Tree::Recursive_PostOrder(Node* root, function<void(Node* node)> func)
{
    if(root == nullptr) return;
    Recursive_PostOrder(root->left, func);
    Recursive_PostOrder(root->right, func);
    func(root);
}
// 전위 순회
void Tree::Recursive_PreOrder(Node* root, function<void(Node* node)> func)
{
    if(root == nullptr) return;    
    func(root);
    Recursive_PreOrder(root->left, func);
    Recursive_PreOrder(root->right, func);
}

전체 소스 코드

정리하면 아래와 같이 구현할 수 있습니다.

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

struct Node{
    Node(int _n, int _x, int _y) : num(_n), x(_x), y(_y) {}
    Node* left{};
    Node* right{};
    int num;
    int x;
    int y;
};
class Tree{
public:
    Tree(int n, int x, int y); 
    void AddNode(int n, int x, int y);
    void AddAnswerPostOrder(vector<vector<int>>& answer);
    void AddAnswerPreOrder(vector<vector<int>>& answer);
    ~Tree();
private:
    Node* root;
    void Recursive_addNode(Node* root, Node* newNode);
    void Recursive_PostOrder(Node* root, function<void(Node* node)> func);    
    void Recursive_PreOrder(Node* root, function<void(Node* node)> func);
};
Tree::~Tree()
{
    auto deleteNode = [](Node* node)
    {
        delete node;
    };
    Recursive_PostOrder(root, deleteNode);
}
void Tree::AddAnswerPostOrder(vector<vector<int>>& answer)
{
    auto AddAnswer = [&answer](Node* node)
    {
        answer[1].push_back(node->num);
    };
    Recursive_PostOrder(root, AddAnswer);
}
void Tree::Recursive_PostOrder(Node* root, function<void(Node* node)> func)
{
    if(root == nullptr) return;
    Recursive_PostOrder(root->left, func);
    Recursive_PostOrder(root->right, func);
    func(root);
}
void Tree::AddAnswerPreOrder(vector<vector<int>>& answer)
{
    auto AddAnswer = [&answer](Node* node)
    {
        answer[0].push_back(node->num);
    };
    Recursive_PreOrder(root, AddAnswer);
}
void Tree::Recursive_PreOrder(Node* root, function<void(Node* node)> func)
{
    if(root == nullptr) return;    
    func(root);
    Recursive_PreOrder(root->left, func);
    Recursive_PreOrder(root->right, func);
}
Tree::Tree(int n, int x, int y)
{
    root = new Node(n,x,y);
}

void Tree::AddNode(int n, int x, int y)
{
    Node* newNode = new Node(n,x,y);
    Recursive_addNode(root, newNode);
}
void Tree::Recursive_addNode(Node* root, Node* newNode)
{
    if(root->x > newNode->x)
    {
        if(root->left == nullptr)
            root->left = newNode;
        else
            Recursive_addNode(root->left, newNode);
    }
    else
    {
        if(root->right == nullptr)
            root->right = newNode;
        else
            Recursive_addNode(root->right, newNode);
    }
}
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    answer.resize(2);
    for(int i = 0; i < nodeinfo.size(); ++i)
    {
        nodeinfo[i].push_back(i + 1);
    }

    auto comp = [](const vector<int>& lhs, const vector<int>& rhs)
    {
        if(lhs[1] > rhs[1]) return true;
        else if(lhs[1] == rhs[1] && lhs[0] < rhs[0]) return true;
        else return false;
    };
    sort(nodeinfo.begin(), nodeinfo.end(), comp);

    Tree tree(nodeinfo[0][2], nodeinfo[0][0], nodeinfo[0][1]);
    for(int i = 1; i < nodeinfo.size(); ++i)
    {
        int num,x,y;
        num = nodeinfo[i][2];
        x = nodeinfo[i][0];
        y = nodeinfo[i][1];
        tree.AddNode(num, x, y);
    }

    tree.AddAnswerPreOrder(answer);
    tree.AddAnswerPostOrder(answer);
    return answer;
}