[프로그래머스] 길 찾기 게임

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

주어진 좌표를 이용해서 트리를 만든 뒤 전위순회, 후휘순회를 통해 답을 출력하는 문제이다. 문제의 핵심은 트리를 생성하는 것인데 y값을 기준으로 내림차순으로 정렬하는데 같은 y값을 가진 점들은 x값을 기준으로 오름차순하여 정렬하면 root노드부터 root의 왼쪽 자식노드, root의 오른쪽 자식 노드 ... 순서로 정렬된다. 노드들을 정렬하고나면 x값을 기준으로 실제 트리를 만들어주면 된다.

코드

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

vector<int> pre, post;

struct Node {
    int x, y, idx;
    Node* left = NULL;
    Node* right = NULL;
};

bool cmp(pair<pair<int, int>, int>& a, pair<pair<int, int>, int>& b) {
    return a.first.second == b.first.second ? a.first.first < b.first.first : a.first.second > b.first.second;
}

// 트리에 노드를 삽입하는 함수
void insertNode(Node* root, int x, int y, int idx) {
    // 트리를 순회하면서 x값 비교를 하기 위한 기준노드
    Node* tmp = root;
    while (true) {
        if (tmp->x > x) {
            if (tmp->left != NULL)
                tmp = tmp->left;
            else {
                Node* newNode = new Node();
                newNode->x = x;
                newNode->y = y;
                newNode->idx = idx;
                tmp->left = newNode;
                break;
            }
        }
        else if (tmp->x < x) {
            if (tmp->right != NULL)
                tmp = tmp->right;
            else {
                Node* newNode = new Node();
                newNode->x = x;
                newNode->y = y;
                newNode->idx = idx;
                tmp->right = newNode;
                break;
            }
        }
    }
}

void preOrder(Node* cur) {
    pre.push_back(cur->idx);
    if (cur->left != NULL) preOrder(cur->left);
    if (cur->right != NULL) preOrder(cur->right);
}

void postOrder(Node* cur) {
    if (cur->left != NULL) postOrder(cur->left);
    if (cur->right != NULL) postOrder(cur->right);
    post.push_back(cur->idx);
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    vector<pair<pair<int, int>, int>> nodes;

    // nodeinfo에서 idx값도 포함하여 nodes 배열에 저장
    for (int i = 0; i < nodeinfo.size(); i++)
        nodes.push_back({ {nodeinfo[i][0], nodeinfo[i][1]}, i + 1 });

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

    // nodes[0]은 루트 노드
    Node* root = new Node();
    root->x = nodes[0].first.first;
    root->y = nodes[0].first.second;
    root->idx = nodes[0].second;

    // nodes[1]부터 트리에 노드를 삽입
    for (int i = 1; i < nodes.size(); i++)
        insertNode(root, nodes[i].first.first, nodes[i].first.second, nodes[i].second);
    preOrder(root);
    postOrder(root);
    answer.push_back(pre);
    answer.push_back(post);
    return answer;
}