[BinaryTree] (프로그래머스 Lv 3) 길 찾기 게임

문제

• 문제 링크
• 문제 설명: 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것. 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 힌트로 주어 각 팀이 스스로 경로를 찾도록 할 계획. 라이언은 아래와 같은 특별한 규칙으로 트리 노드들을 구성한다.
  • 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
  • 모든 노드는 서로 다른 x값을 가진다.
  • 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
  • 자식 노드의 y 값은 항상 부모 노드보다 작다.
  • 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
  • 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

• 이진트리를 구성하는 노드들의 좌표가 담긴 배열 nodeinfo가 매개변수로 주어질 때, 노드들로 구성된 이진트리를 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 반환하는 함수를 작성
• 입력
  • nodeinfo의 길이는 1 이상 10,000 이하
  • nodeinfo[i] 는 i + 1번 노드의 좌표이며, [x축 좌표, y축 좌표] 순으로 들어있다.
  • 모든 노드의 좌표 값은 0 이상 100,000 이하인 정수
  • 트리의 깊이가 1,000 이하인 경우만 입력으로 주어진다.
• 출력: 전위 순회, 후위 순회 결과를 저장한 배열

풀이

• 이진 트리는 비단말 노드가 자식 노드를 최대 2개만 가질 수 있기 때문에 y좌표 내림차순, x좌표 오름차순으로 정렬한 후 값이 큰 y부터 차례대로 삽입하면 x값을 비교하면서 위의 조건들이 자연스레 만족되면서 위 그림과 같이 이진트리가 만들어짐
• 즉, 잘못된 순서로 입력되어지는 경우가 없기 때문에 다음 노드부터 x값 기준으로 부모보다 작으면 왼쪽 자식으로 크면 오른쪽 자식으로 보낸다. 둘 다 자식이 없으면 그 때는 자식을 생성한다.
  • y값이 같은게 중간 레벨에 1개 있거나 3개 이상 있는 경우는 없으므로 제대로 동작
• 맨 처음에 좌표마다 노드 번호를 저장 map<pii, int>
• 주의할 점: 전위 순회, 후위 순회는 일반적으로 알고 있는 순회가 아닌 그림의 순서를 참고해야 함.
• 정답 코드

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;

map<pii, int> m;

struct Node {
    pii c;
    Node* l;
    Node* r;
    
    Node(pii c): c(c), l(nullptr), r(nullptr) {}
    
    void insert(pii p) {
        if (c.X > p.X) {
            if (l) l->insert(p);
            else l = new Node(p);
        } else {
            if (r) r->insert(p);
            else r = new Node(p);
        }
    }
    
    void preorder(vector<int>& v) {
        v.push_back(m[c]);
        if (l) l->preorder(v);
        if (r) r->preorder(v);
    }
    
    void postorder(vector<int>& v) {
        if (l) l->postorder(v);
        if (r) r->postorder(v);
        v.push_back(m[c]);
    }
};

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    for (int i = 0; i < nodeinfo.size(); i++)
        m[{nodeinfo[i][0], nodeinfo[i][1]}] = i+1;
    
    sort(nodeinfo.begin(), nodeinfo.end(), [&](auto& a, auto& b) mutable {
        if (a[1] == b[1]) return a[0] < b[0];
        return a[1] > b[1];
    });
    
    // 이진 트리 생성
    Node* root = new Node({nodeinfo[0][0], nodeinfo[0][1]});
    for (int i = 1; i < nodeinfo.size(); i++)
        root->insert({nodeinfo[i][0], nodeinfo[i][1]});
    vector<int> v1, v2;
    root->preorder(v1); // 전위 순회
    root->postorder(v2); // 후위 순회
    return {v1, v2};
}