(C++) - 프로그래머스(2019 KAKAO BLIND RECRUITMENT) : 길 찾기 게임

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

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

Linked list로 graph를 만든뒤 전위, 후위 순위를 하는 문제였습니다.

 

풀이방법

 1. 노드 번호를 nodeinfo에 추가해줍니다. i번째 nodeinfo는 i+1의 노드번호를 가집니다.

 2. x축에 대해 오름차순으로 정렬해줍니다. 이러면 중간에 적절히 root에 해당하는 가장 큰 y값의 node가 위치하게 됩니다.

 3. tree구조를 struct 형태로 만들어 줍니다. struct는 index번호와 왼쪽, 오른쪽 자식을 가르키는 포인터로 이루어져 있습니다. 자신보다 y축의 값이 더 큰 node들은 자신의 부모에 해당합니다. 가장 큰 값을 부모로 두면서 재귀형태로 연결해줍니다.

 4. 전위 순회, 후위 순회한 결과를 answer에 각각 push해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using vvi = vector<vector<int>>;
using vi = vector<int>;

struct Tree {
    int index;
    Tree *left;
    Tree *right;
};

Tree *makeTree(vvi &nodeinfo , int start, int end) {
    if(start > end) return NULL;
    int maxHeight = nodeinfo[start][1];
    int curNodeIdx = start;
    for(int i = start + 1; i <= end; i++){
        if(maxHeight < nodeinfo[i][1]){
            maxHeight = nodeinfo[i][1];
            curNodeIdx = i;
        }
    }

    Tree *node = new Tree();
    node->index = nodeinfo[curNodeIdx][2];
    node->left = makeTree(nodeinfo,start,curNodeIdx-1);
    node->right = makeTree(nodeinfo,curNodeIdx + 1, end);
    return node;
}

void preOrder(Tree *tree, vi &result){
    if(tree == NULL) return;
    result.push_back(tree->index);
    preOrder(tree->left, result);
    preOrder(tree->right, result);
}

void postOrder(Tree *tree, vi &result){
    if(tree == NULL) return;
    postOrder(tree->left, result);
    postOrder(tree->right, result);
    result.push_back(tree->index);
}

vvi solution(vvi nodeinfo) {
    vvi answer;
    vi pre,post;
    for(int i = 0; i < nodeinfo.size(); i++) nodeinfo[i].push_back(i+1);
    sort(nodeinfo.begin(),nodeinfo.end());
    Tree *tree = makeTree(nodeinfo,0,nodeinfo.size()-1);
    preOrder(tree, pre);
    postOrder(tree, post);
    answer.push_back(pre);
    answer.push_back(post);
    return answer;
}