[프로그래머스/Level 3/C++/2019 카카오 블라이드 채용] 길 찾기 게임

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

- 출처 : 프로그래머스 코딩 테스트 연습

프로그래머스

 

[문제 요약]

- 라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다.

 

- 그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 힌트로 주어 각 팀이 스스로 경로를 찾도록 할 계획이다.

 

- 라이언은 아래와 같은 특별한 규칙으로 트리 노드들을 구성한다.

• 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
• 모든 노드는 서로 다른 x값을 가진다.
• 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
• 자식 노드의 y 값은 항상 부모 노드보다 작다.
• 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
• 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

- 라이언의 규칙에 맞게 이진트리의 노드만 좌표 평면에 그리면 다음과 같다. (이진트리의 각 노드에는 1부터 N까지 순서대로 번호가 붙어있다.

 

- 이제, 노드를 잇는 간선(edge)을 모두 그리면 아래와 같은 모양이 된다.

- 위 이진트리에서 전위 순회(preorder), 후위 순회(postorder)를 한 결과는 다음과 같고, 이것은 각 팀이 방문해야 할 순서를 의미한다.

• 전위 순회 : 7, 4, 6, 9, 1, 8, 5, 2, 3
• 후위 순회 : 9, 6, 5, 8, 1, 4, 3, 2, 7

- 전위 순회를 했을 때 방문하는 노드의 순서와 , 후위 순회를 했을 때 방문하는 노드의 순서를 구하여라

 

 

[문제 조건]

- nodeinfo는 이진트리를 구성하는 각 노드의 좌표가 1번 노드부터 순서대로 들어있는 2차원 배열이다.

• nodeinfo의 길이는 1 이상 10,000 이하이다.
• nodeinfo[i] 는 i + 1번 노드의 좌표이며, [x축 좌표, y축 좌표] 순으로 들어있다.
• 모든 노드의 좌표 값은 0 이상 100,000 이하인 정수이다.
• 트리의 깊이가 1,000 이하인 경우만 입력으로 주어진다.
• 모든 노드의 좌표는 문제에 주어진 규칙을 따르며, 잘못된 노드 위치가 주어지는 경우는 없다.

 

[문제 풀이]

문제에서 주어지는 각 정점의 좌표위치를 이용해서 트리를 만들고 전휘 순회와 후위 순회를 진행해주면 되는 문제다.

 

트리를 구성할 때 중요한 점은 부모노드위 y좌표는 자식 노드의 y좌표보다는 항상 크고, 한 정점 S 의 왼쪽 서브트리에 있는 모든 노드들은 x좌표의 값은 정점 S의 x좌표 값보다 크고, 오른쪽 서브트리에 있는 노드들은 값이 작다.

 

처음에 주어지는 nodeinfo배열의 값에다가 각 노드들의 노드 번호를 추가하여 y좌표를 기준으로 정렬을 했다.

bool cmp(pair<pii,int> &a, pair<pii,int> &b)
{
    return a.first.second > b.first.second;
}
//////////////////////////
.........................
//////////////////////////
for(int i=0; i<nodeinfo.size(); i++)
{
    pair<pii,int> tmp1;
    tmp1.first.first = nodeinfo[i][0]; tmp1.first.second = nodeinfo[i][1];
    tmp1.second = i+1;
    dt[i] = tmp1;
}
sort(dt.begin(), dt.end(), cmp);

pii는 pair<int,int>를 의미한다.

 

 

다음에는 정렬된 배열을 이용해서 이진트리를 구성하였다.

정렬된 배열의 첫 번째 원소를 루트 노드로 설정하여 루트노드의 x값과 현재 비교하는 원소의 x값을 비교하여 왼쪽 서브트리로 보낼 것인지 오른쪽 서브트리로 보낼 것인지 결정하고 가고자 하는 방향에 이미 자식이 있으면 붙혀질 수 있는 노드까지 내려간다.

그렇게 진행하면 예제의 경우 위와 같은 배열이 만들어진다.

 

이 배열을 이용하여 전위 순회와 후위 순회를 진행하면 된다.

 

[소스 코드]

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

#define pii pair<int,int>

using namespace std;

bool cmp(pair<pii,int> &a, pair<pii,int> &b)
{
    return a.first.second > b.first.second;
}

void preorder(vector<vector<int>> &tree, vector<int> &answer, int cur)
{
    answer.push_back(cur);
    if(tree[cur][0] != 0) preorder(tree, answer, tree[cur][0]);
    if(tree[cur][1] != 0) preorder(tree, answer, tree[cur][1]);
}
void postorder(vector<vector<int>> &tree, vector<int> &answer, int cur)
{
    if(tree[cur][0] != 0) postorder(tree, answer, tree[cur][0]);
    if(tree[cur][1] != 0) postorder(tree, answer, tree[cur][1]); 
    answer.push_back(cur);
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    vector<pair<pii,int>> dt;
    vector<vector<int>> tree;
    
    answer.resize(2);
    
    tree.resize(nodeinfo.size()+1);
    for(int i=0; i<=nodeinfo.size(); i++) tree[i].resize(2);
    
    dt.resize(nodeinfo.size());
    for(int i=0; i<nodeinfo.size(); i++)
    {
        pair<pii,int> tmp1;
        tmp1.first.first = nodeinfo[i][0]; tmp1.first.second = nodeinfo[i][1];
        tmp1.second = i+1;
        dt[i] = tmp1;
    }
    sort(dt.begin(), dt.end(), cmp);
   
    int top_node = dt[0].second;
    for(int i=1; i<dt.size(); i++)
    {
        int cur_node = top_node;
        bool flag=false;
        while(!flag)
        {
        //오른쪽
            if(nodeinfo[cur_node-1][0] < dt[i].first.first)
            {
                if(tree[cur_node][1] == 0) {tree[cur_node][1] = dt[i].second; flag = true;}
                else cur_node = tree[cur_node][1];
            }
        //왼쪽
            else if(nodeinfo[cur_node-1][0] > dt[i].first.first)
            {
                if(tree[cur_node][0] == 0) {tree[cur_node][0] = dt[i].second; flag = true;}
                else cur_node = tree[cur_node][0];
            }
        }
    }
    
    preorder(tree, answer[0], dt[0].second);
    postorder(tree, answer[1], dt[0].second);
    return answer;
}

굳