카카오 2018 블라인드 테스트: 길 찾기 게임 C++

https://www.welcomekakao.com/learn/courses/30/lessons/42892

순회는 간단한 부분이기 때문에, 사실 관건은 좌표를 이용해서 트리를 어떻게 만들 것이냐이다.

기본적으로 위에서부터, root를 시작으로 아래로 채워갈 것이기 때문에, 입력받는 좌표를 y값 내림차순으로 정렬한다. y좌표가 동일한 경우 x좌표 오름차순으로 정렬해서, 왼쪽 자식부터 확인할 수 있도록 한다.

정렬을 할 때, 아무런 처리를 해주지 않고 정렬하게 되면, 본인이 원래 몇 번째 인덱스였는지 잃어버리기 때문에, 이후에 순회를 할 수가 없다.

따라서 입력을 받을 당시에, 본인의 인덱스를(노드 번호) 갖고 있도록 처리를 해주어야 한다.

본인은 구조체를 이용했고, 사실 벡터에 그냥 인덱스를 추가해줘도 상관이 없을 것 같다.

트리를 만들 때는, 링크드리스트의 형태를 취해서 만드는 것도 가능하고, 배열의 인덱스를 루트로 해서 하는 방법도 가능하다.

본인은 후자로 구현했다.

#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
 
struct Node {
    int idx, l = 0, r = 0, x, y;
}b[10001];
struct move {
    int l, r;
}m[10001];
bool cmp(Node a, Node b) {
    if (a.y > b.y) return true;
    else if (a.y < b.y) return false;
    else {
        return a.x < b.x;
    }
}
int num;
void makeTree(int root) {
 
    for (int i = 2; i <= num; i++) {
        int cur = root;
        while (1) {
            if (b[i].x < b[cur].x) {
                if (b[cur].l == 0) {
                    b[cur].l = i;
                    break;
                }
                else
                    cur = b[cur].l;
            }
            else {
                if (b[cur].r == 0) {
                    b[cur].r = i;
                    break;
                }
                else
                    cur = b[cur].r;
            }
        }
    }
}
vector<int> pre;
void preOrder(int cur) {
    if (cur == 0) return;
    pre.push_back(cur);
    preOrder(m[cur].l);
    preOrder(m[cur].r);
}
vector<int> pos;
void postOrder(int cur) {
    if (cur == 0) return;
    postOrder(m[cur].l);
    postOrder(m[cur].r);
    pos.push_back(cur);
}
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    num = nodeinfo.size();
 
    for (int i = 1; i <= nodeinfo.size(); i++) {
        b[i].x = nodeinfo[i-1][0];
        b[i].y = nodeinfo[i-1][1];
        //cout << nodeinfo[i - 1][0] << ' ' << nodeinfo[i - 1][1] << '\n';
        b[i].idx = i;
    }
 
    sort(b+1, b + num+1, cmp); //1. y좌표 큰순, 2. x좌표 작은순
    
    makeTree(1); // root의 노드 번호
    
    for (int i = 1; i <= num; i++) {
        m[b[i].idx].l = b[b[i].l].idx;
        m[b[i].idx].r = b[b[i].r].idx;
    }
 
    preOrder(b[1].idx);
    postOrder(b[1].idx);
 
    answer.push_back(pre);
    answer.push_back(pos);
    return answer;
}
 
int main(void) {
    vector<vector<int>> nodeinfo;
    nodeinfo = { {5,3},{11,5}, {13,3}, {3,5}, {6,1}, {1,3}, {8,6}, {7,2}, {2,2} };
    solution(nodeinfo);
    return 0;
}