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

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

프로그래머스

 

 

해결 방법

1. 정렬을 한다. 기준은 , Y값이 가장 높으 순서로, 그다음 x값이 작은 순서대로 나열한다. BFS탐색할때처럼 만들면된다.
2. 맨 첫번째아이템이 root가 되고, 아이템 한개 씩 insertNode를 수행한다.
3. preorder과 postorder를 수행해서 answer에 넣는다.

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

using namespace std;

struct Node{
    int id,x,y;
    Node* left;
    Node* right;
    
    Node(int id, int x, int y):id(id),x(x),y(y),left(nullptr),right(nullptr){}
};


void preorder(vector<int>& answer, Node* top){
    if(top == nullptr) return;
    answer.push_back(top->id);
    preorder(answer, top->left);
    preorder(answer , top->right);
}


void postorder(vector<int>& answer, Node* top){
    if(top == nullptr) return;
    
    postorder(answer, top->left);    
    postorder(answer , top->right);    
    answer.push_back(top->id);
}

Node* insertNode(Node* top, Node* node){
    //여기에 넣기로 결정
    if(top == nullptr) return node;
    
    //새로넣는값이 크다면 오른쪽에  넣기
    if(node->x < top->x) top->left = insertNode(top->left,node);
    else top->right = insertNode(top->right, node);
    
    return top;
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer(2);
    vector<Node*> nodes;
    //노드정보를 기입
    for(int i=0; i<nodeinfo.size();i++){
        nodes.push_back(new Node(i+1,nodeinfo[i][0],nodeinfo[i][1]));
    }
    
    //정렬
    sort(nodes.begin(), nodes.end(), [](Node* a, Node* b){
        if(a->y != b->y) return a->y > b->y; 
        else return a->x < b->x;
    });
    
    Node* root = nodes[0];
    for(int i=1; i<nodes.size(); i++){
        root = insertNode(root, nodes[i]);
    }

    preorder(answer[0],root);
    postorder(answer[1],root);
    return answer;
}

 

마무리하며

 

이진트리 개념은 완벽하게 알고있다고  생각했는데, 코드로 구현을 하려니 struct, 포인터부분에서 많이 헤맸던 문제이다. 개념만 알아서는 문제를 풀 수 없다는 것을 알게되었다. 그리고 아래 부분에서 left 와 right를 nullptr로 명시해주지 않으면, 같은 코드인데 core dump 에러가 발생했다. 처음엔 로직에 문제가 있을거라고 생각했는데, 이런 작은 부분에서 코드가 안돌아가니 많이 힘들었다 ㅠㅠ 

c++언어를 따로 공부해볼까  고민하게 되는 문제였다..

 

struct Node{
    int id,x,y;
    Node* left;
    Node* right;
    
    Node(int id, int x, int y):id(id),x(x),y(y),left(nullptr),right(nullptr){}
};