2019 KAKAO BLIND RECRUITMENT > 길 찾기 게임

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/42892

프로그래머스

 

오랜만에 구조체를 사용하여 문제를 푸느라 다소 어려웠다.

 

문제를 풀기 위해서 Node 구조체를 정의해준 다음 nodeinfo를 바탕으로 이를 초기화해주었다.

 

그런 다음 sort 함수에 람다 함수를 이용하여 문제에 조건에 맞게 정렬해주었다.

 

이 과정을 통해 이진탐색트리로 문제를 풀 수 있다.

 

그런 다음 Node를 순회하면서 left와 right child 중 어느 자리에 위치할 수 있는지를 탐색한다.

 

둘 중 하나지만 이미 노드가 있는 경우 해당 노드를 부모로 하여 재귀적으로 탐색한다.

 

이는 앞서 조건에 맞추어 정렬을 해주었기 때문에 이미 결정된 노드의 위치가 변하는 일이 없어서 가능한 것이다.

 

이렇게 트리를 만들고 나면 preorder와 postorder 방식으로 재귀 탐색하는 것은 간단한 일이다.

 

따라서 각 함수를 재귀적으로 구현한 결과를 return하여 답을 구할 수 있다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 노드 구조체 정의
struct Node {
    int x, y, num;
    Node *left;
    Node *right;
};

// 정렬 기준: y 값이 큰 순서, y가 같다면 x 값이 작은 순서
bool compareNodes(const Node &a, const Node &b) {
    if (a.y == b.y) return a.x < b.x;
    return a.y > b.y;
}

// 재귀를 통해 적절한 위치가 나올 때까지 반복 탐색하여 트리에 삽입
void insertNode(Node* parent, Node* child) {
    if (child->x < parent->x) {
        // 왼쪽 서브트리로 삽입
        if (parent->left == nullptr) parent->left = child;
        else insertNode(parent->left, child);
    } else {
        // 오른쪽 서브트리로 삽입
        if (parent->right == nullptr) parent->right = child;
        else insertNode(parent->right, child);
    }
}

// 전위 순회 함수
void preorder(Node* node, vector<int>& result) {
    if (node == nullptr) return;
    result.push_back(node->num);
    preorder(node->left, result);
    preorder(node->right, result);
}

// 후위 순회 함수
void postorder(Node* node, vector<int>& result) {
    if (node == nullptr) return;
    postorder(node->left, result);
    postorder(node->right, result);
    result.push_back(node->num);
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    int n = nodeinfo.size();
    vector<Node> nodes;
    
    // nodeinfo로부터 노드 초기화
    for (int i = 0; i < n; ++i) {
        nodes.push_back({nodeinfo[i][0], nodeinfo[i][1], i + 1, nullptr, nullptr});
    }
    
    // 주어진 규칙에 따라 노드들을 정렬
    sort(nodes.begin(), nodes.end(), compareNodes);
    
    // 트리 구성
    Node* root = &nodes[0];
    for (int i = 1; i < n; ++i) {
        insertNode(root, &nodes[i]);
    }
    
    // 전위 순회 및 후위 순회 결과 저장
    vector<int> preorder_result;
    vector<int> postorder_result;
    
    preorder(root, preorder_result);
    postorder(root, postorder_result);
    
    return {preorder_result, postorder_result};
}