[프로그래머스/Level 3] 길 찾기 게임 (C++)

programmers.co.kr/learn/courses/30/lessons/42892

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

카카오 기출 유형

 

이진트리를 구현하고 이를 통해 다양한 순회 방법을 구현할 수 있는지 물어보는 문제였습니다.

 

풀이

id=1 x=5,y=3 left=null right=null

id=2 x=11,y=5 left=null right=null

id=3 x=13,y=3 left=null right=null

id=4 x=3,y=5 left=null right=null

id=5 x=6,y=1 left=null right=null

id=6 x=1,y=3 left=null right=null

id=7 x=8,y=6 left=null right=null

id=8 x=7,y=2 left=null right=null

id=9 x=2,y=2 left=null right=null

이진트리를 구성하는 각 좌표를 이용하여 다음과 같이 새로운 구조체 배열을 만들어냅니다. 그리고 이를 y값을 기준으로 내림차순, 같다면 x값을 기준으로 오름차순 정렬을 해줍니다.

 

id=7 x=8,y=6 left=null right=null

id=4 x=3,y=5 left=null right=null

id=2 x=11,y=5 left=null right=null

id=6 x=1,y=3 left=null right=null

id=1 x=5,y=3 left=null right=null

id=3 x=13,y=3 left=null right=null

id=9 x=2,y=2 left=null right=null

id=8 x=7,y=2 left=null right=null

id=5 x=6,y=1 left=null right=null

그러면 다음과 같은 순서로 구조체 배열이 정렬됩니다. 이제 이를 이용해서 루트 노드를 구조체 배열의 0번 인덱스로 설정하고, 이진 트리를 만들어줍니다. 이진 트리를 만들때 다음 특징을 이용해야합니다.

 

• 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
• 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

// 트리를 구성할 노드 추가
void addNode(Node *parent, Node *child) {
    if(child->x < parent->x) {
        if(parent->left == NULL) parent->left = child;
        else addNode(parent->left, child);
    } else {
        if(parent->right == NULL) parent->right = child;
        else addNode(parent->right, child);
    }
}

....

// 이진트리 만들기
Node *root  = &nodes[0];
for(int i = 1; i < size; i++) {
	addNode(root, &nodes[i]);
}

부모 노드의 left 혹은 right가 NULL이면 그대로 child 노드를 가리키게 하고, 만약 이미 가리키는 뭔가가 존재한다면 재귀 호출을 통해 부모 노드를 갱신하고 다시 트리를 타게 됩니다. 이런 과정을 모두 거치면 이진 트리가 완성되고, 전위 순회와 후위 순회를 구현하면 됩니다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

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

int cmp(const Node &a, const Node &b) {
	// x기준 오름차순
    if(a.y == b.y) return a.x < b.x;
    // y기준 내림차순
    return a.y > b.y;
}

// 트리를 구성할 노드 추가
void addNode(Node *parent, Node *child) {
    if(child->x < parent->x) {
        if(parent->left == NULL) parent->left = child;
        else addNode(parent->left, child);
    } else {
        if(parent->right == NULL) parent->right = child;
        else addNode(parent->right, child);
    }
}

// 전위 순회
void preorder(vector<int>& ans, Node *node) {
    if(node == NULL) return;
    
    ans.push_back(node->id);
    
    preorder(ans, node->left);
    preorder(ans, node->right);
}

// 후위 순회
void postorder(vector<int>& ans, Node *node) {
    if(node == NULL) return;
    
    postorder(ans, node->left);
    postorder(ans, node->right);
    
    ans.push_back(node->id);
}

// 중위 순회
// void inorder(vector<int>& ans, Node *node) {
//     if(node == NULL);
    
//     inorder(ans, node->left);
    
//     ans.push_back(node->id);
    
//     inorder(ans, node->right);
// }

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    int size = nodeinfo.size();
    vector<Node> nodes;
    vector<vector<int>> answer { {}, {} };
    
    for(int i = 0; i < size; i++) {
        nodes.push_back({ i + 1, nodeinfo[i][0], nodeinfo[i][1] });
    }
    sort(nodes.begin(), nodes.end(), cmp);
    
    // 이진트리 만들기
    Node *root  = &nodes[0];
    for(int i = 1; i < size; i++) {
        addNode(root, &nodes[i]);
    }
    
    // 전위 순회
    preorder(answer[0], root);
    // 후위 순회
    postorder(answer[1], root);
    
    return answer;
}