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

 

해당 문제는 2019 KAKAO BLIND RECRUITMENT 출제 문제로 공식 해설이 있습니다.

2019 카카오 신입 공채 1차 코딩 테스트 문제 해설

 

해설

traverse(int cur, vector<int> vchild) 는 cur을 루트노드로 자식노드 vchild 를 순회하는 함수이다.

자식 노드들 중에서 cur 노드의 x좌표보다 x좌표가 작은 노드들은 왼쪽서브트리, x좌표가 큰 노드들은 오른쪽서브트리에 위치하게 된다.

cur을 기준으로 왼쪽서브트리와 오른쪽서브트리에 해당하는 배열들을 구성한 뒤, 각각의 배열에서 루트노드를 찾는다.

이때, 트리의 루트 노드는 y좌표가 가장 큰 노드가 된다.

 

전위 순회의 경우, 현재 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리

후위 순회의 경우, 왼쪽 서브트리 -> 오른쪽 서브트리 -> 현재 노드  순으로 순회한다.

 

트리를 순회하면서 전위 순회의 결과 벡터, 후위 순회의 결과 백터를 구한 뒤 {전위 순회 결과, 후위 순회 결과}를 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

vector<int> vpre, vpost;

void traverse(int cur, vector<int> vchild, vector<vector<int>> nodeinfo) {

    vpre.push_back(cur+1);

    int x = nodeinfo[cur][0];
    int y = nodeinfo[cur][1];

    vector<int> leftsub, rightsub;

    //x좌표가 cur노드의 x좌표 보다 작으면 왼쪽서브트리, 크면 오른쪽서브트리
    for (int c : vchild) {
        int a = nodeinfo[c][0];
        int b = nodeinfo[c][1];
        if (a < x) leftsub.push_back(c);
        else rightsub.push_back(c);
    }

    //각 서브트리의 루트 노드를 구해 순회
    auto cmp = [&nodeinfo](int a, int b){return nodeinfo[a][1] > nodeinfo[b][1];};
    sort(leftsub.begin(), leftsub.end(), cmp);
    sort(rightsub.begin(), rightsub.end(), cmp);

    if ((int)leftsub.size()> 0) {
        int next = leftsub[0];
        leftsub.erase(leftsub.begin());
        traverse(next, leftsub, nodeinfo);
    }
    if ((int)rightsub.size() > 0) {
        int next = rightsub[0];
        rightsub.erase(rightsub.begin());
        traverse(next, rightsub, nodeinfo);
    }

    vpost.push_back(cur+1);
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {

    vector<int> child;
    for (int i=0; i<(int)nodeinfo.size(); i++) 
        child.push_back(i);

    //가장 y값이 큰 노드가 루트 노드
    auto cmp = [&nodeinfo](int a, int b){return nodeinfo[a][1] > nodeinfo[b][1];};
    sort(child.begin(), child.end(), cmp);

    int root = child[0];
    child.erase(child.begin());
    traverse(root, child, nodeinfo);

    vector<vector<int>> ans;
    ans.push_back(vpre);
    ans.push_back(vpost);
    return ans;
}