2019 Kakao blind 42892 - 길 찾기 게임(이진 트리 순회) c++ 풀이

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

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

- 뭔가 교과서적인 문제였다. 그동안 백준에서 트리그래프 알고리즘 문제를 풀 때 부모노드 idx만 담는 int 배열로 트리를 구현하곤 했는데, 이렇게 자식정보를 담는 노드를 구현해야되는 문제를 오랜만에 풀어봐서 간만에 알고리즘 전공서를 펴서 트리 순회하는 파트를 복습하는 계기가 됬다. inorder, preorder, postorder 구현보다 트리를 구현하는게 더 어려운 문제였다. 

- y좌표가 크면 클수록 root에 가깝고, x값이 작을 수록 left Node에 가까운 문제 조건을 이용해서 노드 리스트를 만들어주고 정렬하면 항상 맨 위, 맨 왼쪽 노드부터 읽어내려가는 노드 순서가 돤다. 이후 노드 포인터 멤버변수에 재귀적으로 다음 노드주소를 넣어주는 insert 연산을 짜면 된다. 

- 그 뒤 전위, 후위순회 하는 로직을 짜면 된다.

트리 순회 방식 복습: 

preorder전위순회: 루트 - 왼쪽 서브트리 - 오른쪽 서브트리 루왼오

inorder중위순회: 왼쪽 서브트리 -루트 - 오른쪽 서브트리 왼루오

postorder후위탐색: 왼쪽 서브트리 - 오른쪽 서브트리 - 루트 왼오루

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

struct Node {
    int idx, x, y;
    Node* left;
    Node* right;
    
    bool operator<(const Node& other) const { // y내림차순 루트, x는 오름차순
        if(y == other.y) return x < other.x;
        return y > other.y;
    }
};

vector<Node> tree;
vector<vector<int>> answer(2); // 전위, 후위순회 결과

void insert(Node* parent, Node* child) {
    if(child->x < parent-> x) { // child가 더 왼쪽이면
        if(parent->left == NULL) parent->left = child;
        else insert(parent->left, child);
    } else { // child와 같거나 오른쪽이면
        if(parent->right == NULL) parent->right = child;
        else insert(parent->right, child);
    }
}

void visit(Node* node, vector<int>& v) {
    v.push_back(node->idx);
    return;
}

void preorder(Node* node) { // 루트-L-R
    if(node == NULL) return;
    
    visit(node, answer[0]);
    preorder(node->left);
    preorder(node->right);
}

void postorder(Node* node) { // L-R-루트
    if(node == NULL) return;
    
    postorder(node->left);
    postorder(node->right);
    visit(node, answer[1]);
}

// 1. 트리 리스트로 그린다 2.ans[0]은 preorder, ans[1]은 postorder 순회순서 넣기
// y가 크면 root 내림차순, x는 오름차순대로 idx
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    int len = nodeinfo.size();
    tree.resize(len);
    
    for(int i = 0; i<len; ++i) {
        tree[i] = {i+1, nodeinfo[i][0], nodeinfo[i][1]};
    }
    sort(tree.begin(), tree.end());
    
    Node* root = &tree[0];
    for(int i = 1; i<len; ++i) {
        insert(root, &tree[i]);
    }
    
    preorder(root);
    postorder(root);
    
    return answer;
}