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

문제

문제 설명

 

풀이

 

[풀이]

 

문제를 보면 전위 순회와 후위 순회를 나타내는 것은 어렵지 않다. 하지만, 노드의 정보를 바탕으로 그래프를 그리는게 약간 힘들다.

​

조건을 보면 모든 노드는 다른 x값을 갖는다.

이를 이용해 x값의 좌표에 몇번 째 노드인지 값을 저장하는 array를 하나 만들어 결과 값을 출력 할 때 사용한다.

​

또한 트리는 이진트리의 형태이며, 같은 레벨에 있는 좌표는 전부 같은 y 값을 갖는다.

그러므로 y값을 기준으로 노드들을 정리한 다음 레벨을 점차 낮추며 그래프를 그리면 쉽게 이진트리를 그릴 수 있다는 사실을 알 수 있다.

​

[아이디어 정리]

1. 이진트리의 자식 관계를 그리기 위해 y축을 기준으로 Map을 만들어 노드를 정리한다.

​

2. 가장 상위에 있는 부모 노드를 찾는다.

​

3. 이후 y축을 기준으로 레벨을 낮춰가며, 현재 노드의 부모 노드를 찾고 현재 노드가 부모노드의 왼쪽 자식인지, 오른쪽 자식인지 찾는다.

​

4. 이진 트리의 자식 관계를 전부 찾은 후, 전위 순회, 후위 순회 한 값을 출력한다.

​

​

[예시]​

위 예시를 보면 아래와 같이 노드를 정리할 수 있다.

[노드 레벨 별 정보]

6 : 8

5 : 3, 11

3 : 1, 5, 13

2 : 2, 7

1 : 6

​

이를 가장 상위 노드인 y축이 6인 노드부터 그래프를 그리면 다음과 같다.

정리된 노드의 정보를 바탕으로 값이 큰지 작은지를 비교하며 어느 쪽 자식인지 이진 트리를 쉽게 그릴 수 있다.

 

Code

 

 

#include <string>
#include <vector>
#include <map>

using namespace std;
map<int, vector<int>>hashmap;
vector<int> preorder,postorder;
bool flag=false;
int idxList[100001]; // x축에 어떤 idx원소가 있는지 저장
int leftChild[100001];
int rightChild[100001];

void MakePreorder(int node)
{
    preorder.push_back(idxList[node]);
    if (leftChild[node]!=-1){
        MakePreorder(leftChild[node]);
    }
    if (rightChild[node]!=-1)
    {
        MakePreorder(rightChild[node]);
    }
}

void MakePostorder(int node)
{
    if (leftChild[node]!=-1)
    {
        MakePostorder(leftChild[node]);
    }
    if (rightChild[node]!=-1)
    {
        MakePostorder(rightChild[node]);
    }
    postorder.push_back(idxList[node]);
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    int mapKey, stNode;
    fill_n(leftChild,100001,-1);
    fill_n(rightChild,100001,-1);
    vector<pair<int,int>> childV(nodeinfo.size()+1); //pair.first = value, second idx
    for (int i=0; i<nodeinfo.size(); i++)
    {
        mapKey=-nodeinfo[i][1];
        idxList[nodeinfo[i][0]]=i+1;
        if (hashmap.find(mapKey)== hashmap.end()) // end와 같다면 키가 없음
        {
            hashmap[mapKey]=vector<int>(1,nodeinfo[i][0]);
        }
        else
        {
            hashmap[mapKey].push_back(nodeinfo[i][0]);
        }
    }
    int nowValue,nowNode;
    for (const pair<int,vector<int>>& pairIdx :hashmap)
    {
        if (!flag)
        {
            flag=true;
            stNode= pairIdx.second[0];
        }
        else
        {
            for (int i=0; i<pairIdx.second.size(); i++)
            {
                nowNode=stNode;
                nowValue=pairIdx.second[i];
                while (true)
                {
                    if (nowNode>nowValue) // 왼쪽자식
                    {
                        if (leftChild[nowNode]==-1)
                        {
                            leftChild[nowNode]=nowValue;
                            break;
                        }
                        else
                        {
                            nowNode=leftChild[nowNode];
                        }
                    }
                    else //오른쪽 자식
                    {
                        if (rightChild[nowNode]==-1)
                        {
                            rightChild[nowNode]=nowValue;
                            break;
                        }
                        else
                        {
                            nowNode=rightChild[nowNode];
                        }
                    }
                }
            }    
        }
    }
    MakePreorder(stNode);
    MakePostorder(stNode);    
    vector<vector<int>> answer;
    answer.push_back(preorder);
    answer.push_back(postorder);
    return answer;
}

 

---

 

Python의 dictionary는 많이 썼는데, C++ map은 많이 안 써봐서 사용하는게 가장 힘들었다;;

 

프로그래머스