프로그래머스 - 길 찾기 게임

출처 : programmers.co.kr/learn/courses/30/lessons/42892

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

 

고려사항

• 한 번 꼬은 x 좌표 기준의 이진 탐색 트리, 순회 문제!
• y 좌표 : ( 노드 번호, x 좌표 ) 꼴로 정보 취합하기. ( 69 - 72 )
• y 좌표가 큰 순서로 이진 트리에 삽입!
• 주의 - 트리의 높이는 1000 이하지만, y 좌표의 값은 0 ~ 100000 까지 가능하다.
  62 라인 처럼 10001 크기의 벡터를 선언하거나 map 자료 구조를 사용하면 된다.
  ( 인덱스, 레벨이 큰 순서부터 집어넣어야 해서 편하게 벡터로 구현했다. map 의 역순탐방이 가능하면 map 사용이 좋을지도.. )
• 27 -32, 34 - 39 라인 처럼 다음 노드를 삽입할 때,
  cur->left, right 가 NULL 이라면 , cur->left, right = newNode 연결 해줘야 한다.
  처음 코드는 while(cur) 의 조건을 믿고, cur = cur->left, right 로 탐방을 하다가
  빈 공간, NULL 이라면 while을 빠져나오고 cur = newNode 를 했더니 트리 구성이 안되었었다..

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
struct node{
    int num;
    int x;
    node *left;
    node *right;
 
    node(int newNum, int newX){
        num = newNum;
        x = newX;
        left = NULL;
        right = NULL;
    }
};
 
void insert(node *cur, int newNum, int newX){
    node *newNode = new node(newNum, newX);
 
    while(cur){
        if(cur->x > newX){
            if(cur->left){
                cur = cur->left;
            }else{
                cur->left = newNode;
                break;
            }
        }else{
            if(cur->right){
                cur = cur->right;
            }else{
                cur->right = newNode;
                break;
            }
        }
    }
}
 
void preorder(node *cur, vector<int> &v){
    if(cur){
        v.push_back(cur->num);
        preorder(cur->left, v);
        preorder(cur->right, v);
    }
}
 
void postorder(node *cur, vector<int> &v){
    if(cur){
        postorder(cur->left, v);
        postorder(cur->right, v);
        v.push_back(cur->num);
    }
}
 
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    vector<pair<int, int>> info[100001];
    vector<int> pre;
    vector<int> post;
    int len = nodeinfo.size();
    int level = -1;
    node *root;
 
    for(int i=0;i<len;++i){
        info[nodeinfo[i][1]].push_back({i+1, nodeinfo[i][0]});
        level = max(level, nodeinfo[i][1]);
    }
 
    root = new node(info[level][0].first, info[level][0].second);
    for(int i=level-1;i>=0;--i){
        for(pair<int, int> p : info[i]){
            insert(root, p.first, p.second);
        }
    }
 
    preorder(root, pre);
    postorder(root, post);
 
    answer.push_back(pre);
    answer.push_back(post);
 
    return answer;
}