[C++로 풀이] 길 찾기 게임 (이진 탐색 트리)⭐⭐⭐

Date: 2021.02.16 Updated: 2021.02.16

카테고리: Programmers

📌 길 찾기 게임

난이도 ⭐⭐⭐

🚀 문제

순서대로 [5, 3], [11, 5] 가 각각 1, 2번 노드가 된다.
이 문제의 경우 이진 탐색 트리의 크기 비교 기준은 x 좌표값이 된다. (data 인 몇 번 노드인지가 비교 기준이 아니다!)

🚀 내 풀이 ⭕

같은 레벨에 있는 노드는 같은 y 좌표를 가진다.
자식 노드의 y값은 항상 부모 노드보다 작다.

임의의 노드 V의 왼쪽 서브 트리에 있는 모든 노드의 x 값은 V의 x값보다 작다.
임의의 노드 V의 오른쪽 서브 트리에 있는 모든 노드의 x 값은 V의 x값보다 크다.
모든 노드는 서로 다른 x값을 가진다.

“이진 탐색 트리” 문제!

y 값 👉 레벨을 구분한다. y값이 높을 수록 높은 레벨. 루트 노드가 가장 y값이 크겠다.
x 값 👉 이진 탐색 트리의 비교 기준이 된다.
- 예제의 경우 9 노드는 [2,2] 좌표
  - 7 보다 x 값이 작다. 따라서 7의 “왼쪽” 서브트리에 속한다. [8,6] 좌표
  - 4 보다 x 값이 작다. 따라서 4의 “왼쪽” 서브트리에 속한다. [3,5] 좌표
  - 6 보다 x 값이 크다. 따라서 6의 “오른쪽” 서브트리에 속한다. [1,3] 좌표
- 이렇게 직속 부모뿐만 아니라 재귀적으로 조상들과의 관계에서도 만족되는 자리에 속해야 한다.
  - x값이 더 작을시 왼쪽으로
  - x값이 더 클시 오른쪽으로

N이라는 노드의 왼쪽 서브트리의 모든 노드들은 N 보다 작다. 반면 N의 오른쪽 서브트리의 모든 노드들은 N보다 크다. 이진 탐색 트리의 모든 노드들은 이 관계를 재귀적으로 만족해야 한다.

풀이 순서

1️⃣ Node로 묶기 (좌표와 번호와 왼쪽 자식이 누군지, 오른쪽 자식이 누군지를 함께 묶어 관리할 수 있도록)
2️⃣ 이진 탐색 트리로 Node 를 관리. 모든 노드의 왼쪽 자식, 오른쪽 자식 세팅!!!
- 추가가 될 때 모든 조상, 부모 노드들과 비교를 하여 왼쪽 자식으로 들어갈지 오른쪽 자식으로 들어갈지 각각 비교하여 어느 자리에 추가할지 결정해야 한다.
  - 루트 노드부터 비교하면서 왼쪽 서브트리로 갈지 오른쪽 서브트리로 갈지 결정하면서 내려오다가 자식이 없는 위치에 도달하면 그 때 그 노드의 자식으로 추가하면 된다.
3️⃣ 이진 탐색 트리로 전위 순회
4️⃣ 이진 탐색 트리로 후위 순회

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

using namespace std;

class Node 
{
public:
    int data;
    int x;
    int y;
    Node* leftChild = NULL;
    Node* rightChild = NULL;

    Node(int _data, int _x, int _y, Node* _leftChild, Node* _rightChild)
        :data(_data), x(_x), y(_y), leftChild(_leftChild), rightChild(_rightChild)
    { }
};

void BST_InsertNode(Node* tree, Node* node)
{
    if (node->x < tree->x) {
        if (tree->leftChild == NULL) {
            tree->leftChild = node;
            return;
        }
        else
            BST_InsertNode(tree->leftChild, node);
    }
    else if (node->x > tree->x) {
        if (tree->rightChild == NULL) {
            tree->rightChild = node;
            return;
        }
        else
            BST_InsertNode(tree->rightChild, node);
    }
}

void BST_PreOrder(Node* tree, vector<int>& pre)
{
    if (tree == NULL)
        return;
    pre.push_back(tree->data);
    BST_PreOrder(tree->leftChild, pre);
    BST_PreOrder(tree->rightChild, pre);
}

void BST_PostOrder(Node* tree, vector<int>& pos)
{
    if (tree == NULL)
        return;
    BST_PostOrder(tree->leftChild, pos);
    BST_PostOrder(tree->rightChild, pos);
    pos.push_back(tree->data);
}

bool cmp(Node& a, Node& b)
{
    if (a.y == b.y)
        return a.x < b.x;
    return a.y > b.y;
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) 
{
    vector<vector<int>> answer;
    
    vector<Node> nodes;
    for (int i = 0; i < nodeinfo.size(); ++i)
        nodes.push_back(Node(i + 1, nodeinfo[i][0], nodeinfo[i][1], NULL, NULL));
    sort(nodes.begin(), nodes.end(), cmp);

    for (int i = 1; i < nodes.size(); ++i)
        BST_InsertNode(&nodes[0], &nodes[i]);

    vector<int> pre;
    BST_PreOrder(&nodes[0], pre);

    vector<int> pos;
    BST_PostOrder(&nodes[0], pos);

    answer.push_back(pre);
    answer.push_back(pos);

    return answer;
}

1️⃣ Node 로 묶어서 관리

class Node 
{
public:
    int data;
    int x;
    int y;
    Node* leftChild = NULL;
    Node* rightChild = NULL;

    Node(int _data, int _x, int _y, Node* _leftChild, Node* _rightChild)
        :data(_data), x(_x), y(_y), leftChild(_leftChild), rightChild(_rightChild)
    { }
};

정렬 하면 정렬 전 몇번째 노드였었는지 data를 기억해야 하고, 또한 해당 노드의 왼쪽 자식, 오른쪽 자식에 대한 정보도 알아야하기 때문에 Node 클래스 (또는 구조체)를 만들어 함께 관리하는게 좋겠다.

bool cmp(Node& a, Node& b)
{
    if (a.y == b.y)
        return a.x < b.x;
    return a.y > b.y;
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) 
{
    vector<vector<int>> answer;
    
    vector<Node> nodes;
    for (int i = 0; i < nodeinfo.size(); ++i)
        nodes.push_back(Node(i + 1, nodeinfo[i][0], nodeinfo[i][1], NULL, NULL));
    sort(nodes.begin(), nodes.end(), cmp);

nodes 벡터에 nodeinfo 원소들을 바탕으로 Node 객체를 만들어 넣는다. (왼쪽 자식, 오른쪽 자식은 “이진 탐색 트리”로서 추가될 때 알 수 있다.)
추후 높은 레벨(조상, 부모들)부터 차례대로 미리 왼쪽 자식, 오른쪽 자식을 설정해줘야 하기 때문에 정렬 한다. 이진 탐색 트리에 추가할 때 조상부터 내려오며 크기를 비교하면서 내려올건데 자식이 없는 곳에 도달할 때 그 위치에 추가할 것이기 때문에 이 작업은 높은 레벨의 노드부터 진행되야 하기 때문에 정렬하는 것이다.
- y 값이 큰게 앞에 오도록 함. 즉, 조상일 수록 앞에 오게! (정렬 후 nodes[0]는 루트 노드가 될 것)
- y 값이 같다면 x 값이 작은게 앞에 오도록 함. (왼쪽이 오른쪽보단 먼저)

2️⃣ 이진 탐색 트리에 추가 (=알맞는 자리에 추가되기 = 왼쪽, 오른쪽 자식 세팅)

void BST_InsertNode(Node* tree, Node* node)
{
    if (node->x < tree->x) { // 현재 재귀 단계에서의 트리의 루트와 크기 비교 (서브트리의 루트)
        if (tree->leftChild == NULL) { // 루트보다 작은데 마침 루트에게 왼쪽 자식이 없다면 루트의 왼쪽 자식으로 세팅 후 종료
            tree->leftChild = node;
            return;
        }
        else
            BST_InsertNode(tree->leftChild, node); // 루트보다 작은데 루트에게 왼쪽 자식이 있다면 거기에 추가될 수 없으므로 더 내려가야 함. 왼쪽 서브트리로 내려가기.
    }
    else if (node->x > tree->x) {  // 루트보다 큰데 마침 루트에게 오른쪽 자식이 없다면 루트의 오른쪽 자식으로 세팅 후 종료
        if (tree->rightChild == NULL) {
            tree->rightChild = node;
            return;
        }
        else
            BST_InsertNode(tree->rightChild, node); // 루트보다 큰데 루트에게 오른쪽 자식이 있다면 거기에 추가될 수 없으므로 더 내려가야 함. 오른쪽 서브트리로 내려가기.
    }
}

    for (int i = 1; i < nodes.size(); ++i)
        BST_InsertNode(&nodes[0], &nodes[i]);

이진 탐색 트리에 추가 된다는 것은 곧 조상부터 크기를 비교며 내려오면서 누군가의 왼쪽, 오른쪽 자식으로 세팅된다는 것이다.

nodes는 Node 들을 높은 레벨의 노드들이 먼저오게끔 정렬이 되어 있는 상태다.(nodes[0]은 루트 노드가 됨) 모든 노드들에 대해 루트 노드부터 시작하여 내려오면서 조상들과 크기를 비교하면서 내려온다. 쭉 내려오다가 자식이 없는 노드의 자식으로 세팅 되고 빠져나오면 된다.

루트 노드 제외하고 그 이후 노드부터 진행한다. (i = 1)

BST_InsertNode(Node* tree, Node* node)
- tree 를 루트로 하는 서브트리로 재귀호출 하면서 내려온다.
  - 왼쪽 서브 트리의 루트로 호출하면 왼쪽으로 내려가는 것이고
  - 오른쪽 서브 트리의 루트로 호출하면 오른쪽으로 내려가는 것이 된다.

크기 비교 기준 : x

“3” 노드의 경우
- “7” 노드의 x 보다 크다. 👉 오른쪽 자식 “2”를 루트로 한 서브트리 재귀 호출
- “2” 노드의 x 보다 크다. 👉 “2”의 오른쪽 자식은 없으므로 “2”의 오른쪽 자식으로 세팅하고 종료. “2” 노드의 오른쪽 자식이 누군지가 세팅된다.
“8” 노드의 경우
- “7” 노드의 x 보다 작다. 👉 왼쪽 자식 “4”를 루트로 한 서브트리 재귀 호출
- “4” 노드의 x 보다 크다. 👉 오른쪽 자식 “1”를 루트로 한 서브트리 재귀 호출
- “1” 노드의 x 보다 크다. 👉 “1”의 오른쪽 자식은 없으므로 “1”의 오른쪽 자식으로 세팅하고 종료. “1” 노드의 오른쪽 자식이 누군지가 세팅된다.

3️⃣ 순회

전위 순회 순서 👉 7 4 6 9 1 8 5 2 3
후위 순회 순서 👉 9 6 5 8 1 4 3 2 7

🔥 전위 순회

void BST_PreOrder(Node* tree, vector<int>& pre)
{
    if (tree == NULL)
        return;
    pre.push_back(tree->data);
    BST_PreOrder(tree->leftChild, pre);
    BST_PreOrder(tree->rightChild, pre);
}

    vector<int> pre;
    BST_PreOrder(&nodes[0], pre);

    answer.push_back(pre);

나의 왼쪽 서브트리의 노드들과 오른쪽 서브트리의 노드들을 순회하기 전에 나를 먼저 출력한다. (pre에 출력 순서대로 원소 들어가게 됨)

🔥 후위 순회

void BST_PostOrder(Node* tree, vector<int>& pos)
{
    if (tree == NULL)
        return;
    BST_PostOrder(tree->leftChild, pos);
    BST_PostOrder(tree->rightChild, pos);
    pos.push_back(tree->data);
}

    vector<int> pos;
    BST_PostOrder(&nodes[0], pos);

    answer.push_back(pos);

나의 왼쪽 서브트리의 노드들과 오른쪽 서브트리의 노드들을 순회를 모두 마친 후에 나를 먼저 출력한다. (pre에 출력 순서대로 원소 들어가게 됨)

💡

이진 탐색 트리 에 대한 더 자세한 설명은 이 포스트를 참고해주세요.

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️