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

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

문제 링크

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct Node {
    int num;
    int val;
    Node *left;
    Node *right;
} Node;
vector <int> pre;
vector <int> post;

int cmp(vector<int> a, vector<int> b) {
    if (a[1] >= b[1]) {
        if (a[1] == b[1]) {
            if (a[0] > b[0]) {
                return true;
            }
            return false;
        }
        return true;
    }
    return false;
}

void preOrder(Node * head){
    if(head == NULL) return;
    pre.push_back(head->num);
    preOrder(head->left);
    preOrder(head->right);
}
void postOrder(Node * head){
    if(head == NULL) return;
    postOrder(head->left);
    postOrder(head->right);
    post.push_back(head->num);
}
Node * createNode(int val, int num){
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->val = val;
    newNode->num = num;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;

    for (int i = 0; i < nodeinfo.size(); i++) nodeinfo[i].push_back(i + 1);
    sort(nodeinfo.begin(), nodeinfo.end(), cmp);

    Node *head = createNode(nodeinfo[0][0], nodeinfo[0][2]);
    int level = nodeinfo[0][1];  // 6
    
    //트리 구현
    for (int i = 1; i < nodeinfo.size(); i++) {
        Node *cur = head;

        int now_val = nodeinfo[i][0];
        int now_level = nodeinfo[i][1];
        int now_num = nodeinfo[i][2];

        //값 비교
        while (1) {
            if (cur->val < now_val) {
                if (cur->right != NULL)
                    cur = cur->right;
                else {
                    cur->right = createNode(now_val, now_num);
                    break;
                }
            } else {
                if (cur->left != NULL)
                    cur = cur->left;
                else {
                    cur->left = createNode(now_val, now_num);
                    break;
                }
            }
        }
    }

    preOrder(head);
    postOrder(head);

    answer.push_back(pre);
    answer.push_back(post);

    return answer;
}

• 트리 구현 문제.
• nodeinfo에 들어온 순서를 추가 해 준다.
• nodeinfo를 y가 큰 순서, x가 큰 순서대로 정렬을 해 준다.
• 다음은 그냥 트리 구현
• 전위순회, 후위순회 진행하면 끝