[프로그래머스][2019 KAKAO BLIND][C++] 길 찾기 게임

문제

프로그래머스 2019 KAKAO BLIND RECRUITMENT - 길 찾기 게임 (Level 3)

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

 

---

문제 풀이

접근 방식

이 문제는 2019 카카오 블라인드 공채 1차 코딩테스트 5번 문제로,

이진 트리를 만들어 전위 순회와 후위 순회를 수행하는 문제이다.

 

이진 트리를 만들기 위해 Node 구조체를 만들어 x, y, index, 왼쪽 노드, 오른쪽 노드를 저장할 수 있도록 하였고,

주어진 nodeinfo에 인덱스를 추가한 후,

y값 기준 내림차순, x값 기준 오름차순으로 정렬해주었다.

 

정렬된 nodeinfo 벡터를 Node를 활용하여 트리 구조로 저장해주었고,전위 순회, 후위 순회 함수를 만들어서 답을 도출하였다.

 

---

풀이 코드 - C++

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

using namespace std;

struct Node {
    int x, y, index;
    Node *left;
    Node *right;
};

bool cmp(vector<int> &a, vector<int> &b) {
    if (a[1] == b[1])
        return a[0] < b[0];
    else
        return a[1] > b[1];
}

// 전위 순회
vector<int> precircuit(const Node *node, vector<int> &pre) {
    pre.push_back(node->index);
    if (node->left != NULL)
        precircuit(node->left, pre);
    if (node->right != NULL)
        precircuit(node->right, pre);
    return pre;
}

 // 후위 순회
vector<int> postcircuit(const Node *node, vector<int> &post) {
    if (node->left != NULL)
        postcircuit(node->left, post);
    if (node->right != NULL)
        postcircuit(node->right, post);
    post.push_back(node->index);
    return post;
}


vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    // 인덱스 추가
    for (int i = 0; i < nodeinfo.size(); i++)
        nodeinfo[i].push_back(i + 1);

    // y값 내림차순, x값 오름차순 정렬
    sort(nodeinfo.begin(), nodeinfo.end(), cmp);

    // 트리 저장
    Node root = { nodeinfo[0][0], nodeinfo[0][1], nodeinfo[0][2], NULL, NULL };
    Node * iter;
    for (int i = 1; i < nodeinfo.size(); i++) {
        iter = &root;
        while (1) {
            if (iter->x > nodeinfo[i][0]) {
                if (iter->left == NULL) {
                    iter->left = new Node{nodeinfo[i][0], nodeinfo[i][1], nodeinfo[i][2], NULL, NULL};
                    break;
                }
                else
                    iter = iter->left;
            }
            else {
                if (iter->right == NULL) {
                    iter->right = new Node{nodeinfo[i][0], nodeinfo[i][1], nodeinfo[i][2], NULL, NULL};
                    break;
                }
                else
                    iter = iter->right;
            }
        }        
    }

    // 전위 순회, 후위 순회
    vector<vector<int>> answer;
    vector<int> pre;
    vector<int> post;
    answer.push_back(precircuit(&root, pre));
    answer.push_back(postcircuit(&root, post));
    return answer;
}

실행 결과

실행 결과 : 100.0