프로그래머스 - 길찾기 게임

 

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

vector<int> preOrder;
vector<int> postOrder;

void PostOrder(vector<vector<int>>& nodes, int x , int y, int nodeNum, int minX, int maxX)
{
    if(y < 0) return;
   
    vector<int> leftNode;
    vector<int> rightNode;
    vector<vector<int>> leftNodes;
    vector<vector<int>> rightNodes;
    for(vector<int> node : nodes)
    {
        if(y <= node[1]) continue;
        if(x < node[0]) rightNodes.push_back(node);
        if(x > node[0]) leftNodes.push_back(node);
    }
    int findingY = y;
    while(leftNode.empty())
    {
        findingY--;
        int distance = 999999;
        for(vector<int> node : leftNodes)
        {
            if(node[1] != findingY || x < node[0] ) continue;
            if(node[0] < minX) continue;
            int localDistance = x - node[0];
            if(localDistance < distance)
            {
                leftNode = {node[0], node[1], node[2]};
            }
        }
        if(findingY < 0) break;
    }
    findingY = y;
    while(rightNode.empty())
    {
        int distance = 999999;
        findingY--;
        for(vector<int> node : rightNodes)
        {
            if(node[1] != findingY || x > node[0]  ) continue;
            if(node[0] > maxX) continue;
            int localDistance = node[0] - x;
            if(localDistance < distance)
            {
                rightNode = {node[0], node[1], node[2]};
            }
        }
        if(findingY < 0) break;
    }
    if(!leftNode.empty())
    {
        PostOrder(leftNodes, leftNode[0], leftNode[1], leftNode[2], minX, x);    
    }
    if(!rightNode.empty())
    {
        PostOrder(rightNodes, rightNode[0], rightNode[1],rightNode[2], x, maxX);   
    }
    postOrder.push_back(nodeNum);
    
}

void PreOrder(vector<vector<int>>& nodes, int x, int y, int nodeNum , int minX, int maxX)
{
    if(y < 0) return;
    preOrder.push_back(nodeNum);
    vector<int> leftNode;
    vector<int> rightNode;
    vector<vector<int>> leftNodes;
    vector<vector<int>> rightNodes;
    for(vector<int> node : nodes)
    {
        if(y <= node[1]) continue;
        if(x < node[0] && x >= minX) rightNodes.push_back(node);
        if(x > node[0] && x <= maxX) leftNodes.push_back(node);
    }
    int findingY = y;
    while(leftNode.empty())
    {
        findingY--;
        int distance = 999999;
        for(vector<int> node : leftNodes)
        {
            if(node[1] != findingY) continue;
            int localDistance = x - node[0];
            
            if(localDistance < distance)
            {
                leftNode = {node[0], node[1], node[2]};
            }
        }
        if(findingY < 0) break;
    }
    findingY = y;
    while(rightNode.empty())
    {
        int distance = 999999;
        findingY--;
        for(vector<int> node : rightNodes)
        {
            if(node[1] != findingY) continue;
            int localDistance = node[0] - x;
            if(localDistance < distance)
            {
                rightNode = {node[0], node[1], node[2]};
            }
        }
        if(findingY < 0) break;
    }
    if(!leftNode.empty())
    {
        PreOrder(leftNodes, leftNode[0], leftNode[1], leftNode[2], minX, x);    
    }
    if(!rightNode.empty())
    {
        PreOrder(rightNodes, rightNode[0], rightNode[1], rightNode[2], x, maxX);   
    }
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    
    for(int i = 0 ; i < nodeinfo.size(); i++)
    {
        nodeinfo[i].push_back(i+1);
    }
    
    sort(nodeinfo.begin(), nodeinfo.end(), 
         [](vector<int> v1, vector<int> v2)
         -> bool 
         { 
             if(v1[1] == v2[1])
             {
                 return v1[0] > v2[0] ;
             }
             else
             {
                 return v1[1] > v2[1] ;
             }
         });
    
    PreOrder(nodeinfo, nodeinfo[0][0], nodeinfo[0][1], nodeinfo[0][2], 0 , 100000);
    PostOrder(nodeinfo, nodeinfo[0][0], nodeinfo[0][1], nodeinfo[0][2], 0 , 100000);
    answer.push_back(preOrder);
    answer.push_back(postOrder);
    return answer;
}