[프로그래머스, C++] 길 찾기 게임

문제 링크

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

 

 

 

풀이

전위 순회(preorder), 후위 순회(postorder)를 리턴하는 문제다.

Node 구조체를 만들어 order하였다.

 

1단계) node들을 vector 컨테이너에 담기

2단계) vector 컨테이너에 있는 node들을 y값으로 정렬(순회하면서 노드들을 추가하기 위해)

3단계) 이진트리 생성(y값은 미리 정렬했으니 x값만 신경썼다)

- 부모의 x보다 작으면 left, 부모의 x보다 크면 right

4단계) order()

- 전위 순회는 먼저 방문을 하고, 후위순회는 자식 노드가 없을 때 방문을 하게했다.

 

 

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

using namespace std;

// 각 팀이 같은 곳을 다른 순서로 방문해서 먼저 순회 마친 팀이 승리하는 게임 구상
// x, y 정수
// 같은 level은 같은 y 좌표값
// 자식 노드는 부모 노드보다 y값 작다
// 임의의 노드 V 기준, 왼쪽 서브트리의 모든 노드는 x값이 V의 X값보다 작음
// 임의의 노드 V 기준, 오른쪽 서브트리의 모든 노드는 x값이 V의 X값보다 큼
// 각 노드는 1~N 번호가 붙음
// 각 팀의 preorder, postorder는 각 팀이 방문해야 할 순서

typedef struct Node{
    int x, y, n;
    Node *left;
    Node *right;
    Node(int _x, int _y, int _n){
        x = _x;
        y = _y;
        n = _n;
        left = NULL;
        right  = NULL;
    }
}Node;

bool cmp(Node n1, Node n2){
    return n1.y > n2.y;
}

void insert(Node* parent, Node* child){
    if(parent->x > child->x){           // left로 놓기
        if(parent->left != NULL) insert(parent->left, child);
        else parent->left = child;
    }
    else if(parent->x < child->x){      // right로 놓기
        if(parent->right != NULL) insert(parent->right, child);
        else parent->right = child;
    }
}

void order(Node* node, vector<vector<int>>& v){
    v[0].push_back(node->n);
    if(node->left != NULL) order(node->left, v);
    if(node->right != NULL) order(node->right, v);
    v[1].push_back(node->n);
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer(2);
    vector<Node> nodes;
    
    // Node 추가
    for(int i=0; i<nodeinfo.size(); i++){
        int x = nodeinfo[i][0];
        int y = nodeinfo[i][1];
        int n = i+1;
        Node node(x, y, n);
        nodes.push_back(node);
    }
    
    // y 값으로 정렬
    sort(nodes.begin(), nodes.end(), cmp);
    
    // 이진트리 생성
    for(int i=1; i<nodes.size(); i++){
        insert(&nodes[0], &nodes[i]);       // root부터
    }

    // (pre, post)order
    order(&nodes[0], answer);
    
    return answer;      // preorder, postorder한 것을 순서대로 반환
}