길 찾기 게임 (c++)

문제

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

설명

단계별로 끊어서 설명하겠습니다.

• 문제 설명을 읽어보면 트리를 구성하는 정보들을 나타냅니다, x, y좌표 현재 노드와 왼쪽자식, 오른쪽 자식에 대한 비교값

• 트리 구성정보를 통해 트리를 구성합니다

• 필요한 정보는 기준이되는 노드, 위치를 찾을 자식 예비 자식노드

  void MakeBinaryTree(Tree * Root, Tree * Child) {
  
    // 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
    if(Root -> x > Child -> x) {
        if(Root -> Left ==  NULL) {
            Root -> Left = Child;
            return ;
        }
        else MakeBinaryTree(Root -> Left, Child); 
    } 
    else {
        // 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.
        if(Root -> Right == NULL) {
            Root -> Right  = Child;
            return ;
        }
        else MakeBinaryTree(Root -> Right, Child);
    }
  }

• 전위 순회, 후위 순회 내용

void PostOrder(Tree * Root, vector<int> &anwer) {

  if(Root == NULL) return;
  PostOrder(Root -> Left, anwer);
  PostOrder(Root -> Right, anwer);
    anwer.push_back(Root -> idx);
}

void preOrder(Tree * Root, vector<int> &answer) {

    if(Root == NULL) return ;
    answer.push_back(Root -> idx);
    preOrder(Root -> Left, answer);
    preOrder(Root -> Right, answer);
}

• 문제 설명에 맞게 정렬한 내용

bool cmp(Tree a, Tree b) {
    if(a.y > b. y) return true;
    else if(a. y == b.y) {
        if(a.x < b.x) return true;
    }

    return false;
}

소스

#include <string>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

struct Tree {

    int idx;
    int x;
    int y;
    Tree *Left;
    Tree *Right;

};

bool cmp(Tree a, Tree b) {
    if(a.y > b. y) return true;
    else if(a. y == b.y) {
        if(a.x < b.x) return true;
    }

    return false;
}
//기준이 되는 노드, 위치를 찾을 노드 
void MakeBinaryTree(Tree * Root, Tree * Child) {

    // 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
    if(Root -> x > Child -> x) {
        if(Root -> Left ==  NULL) {
            Root -> Left = Child;
            return ;
        }
        else MakeBinaryTree(Root -> Left, Child); 
    } 
    else {
        // 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.
        if(Root -> Right == NULL) {
            Root -> Right  = Child;
            return ;
        }
        else MakeBinaryTree(Root -> Right, Child);
    }
}
//후위 순회, 왼쪽 왼쪽 쭉 가다가 없으면 해당 부모의 RIGHT 쭉쭉 후위는 Root를 맨 나중에 순회하는 것! 
void PostOrder(Tree * Root, vector<int> &anwer) {

  if(Root == NULL) return;
  PostOrder(Root -> Left, anwer);
  PostOrder(Root -> Right, anwer);
    anwer.push_back(Root -> idx);
}

void preOrder(Tree * Root, vector<int> &answer) {

    if(Root == NULL) return ;
    answer.push_back(Root -> idx);
    preOrder(Root -> Left, answer);
    preOrder(Root -> Right, answer);
}
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;

    vector<Tree> v;
    //이진트리 정렬하기 
    for(int i = 0 ; i < nodeinfo.size(); i++) {
        int x = nodeinfo[i][0];
        int y = nodeinfo[i][1];

        v.push_back({i + 1, x, y, NULL, NULL});
    }
    sort(v.begin(), v.end(), cmp);
    Tree *Root = &v[0];

    // 이진트리 만들기 
    for(int i = 1 ; i < v.size(); i++) {
        MakeBinaryTree(Root, &v[i]);
    }
    vector<int> preorder;
    vector<int> postorder;

    preOrder(Root, preorder);
    PostOrder(Root, postorder);

    answer.push_back(preorder);
    answer.push_back(postorder);
    return answer;
}