[ 프로그래머스 길 찾기 게임 (Lv3) ] (C++)

프로그래머스의 길찾기게임(Lv3) 문제이다.

 

[ 문제풀이 ]

트리가 주어졌을 때, 해당 트리의 전위순회와 후위순회 순서를 구해야 하는 문제이다.

문제를 단계별로 한 단계씩 알아가보자.

 

#1. Node관리

이 문제는 트리의 Node들을 가지고 과정을 진행하고 정답을 도출해 내야 하는 문제이다.

따라서, Node들을 관리하기 위해서 본인은 구조체를 하나 정의해 주었다.

그럼 ! 구조체에 필요한 멤버변수들을 뭐가 있을지 생각을 해보자.

1. 해당 Node의 (x , y)좌표 정보가 필요할 것이다.

2. 해당 Node의 번호가 필요할 것이다.

- 번호가 필요한 이유는 정답 도출을 위해서이다. 전위든 후위든 결국 그 순서를 Node의 번호 순서대로 출력을 해야 하

  는데 이를 위해서 Node의 번호 또한 우리가 알고 있어야 할 정보 중에 하나가 된다.

3. 자식 Node에 대한 정보가 필요할 것이다.

- Tree구조로 진행되므로, 해당 Node의 왼쪽 자식에 대한 정보, 오른쪽 자식에 대한 정보가 필요할 것이다.

  이를 바탕으로 전위 , 후위 순회를 진행할 것이다.

 

그래서 본인은 ! 위와 같이 총 5개의 정보를 멤버변수로 갖는 구조체를 하나 만들어 주었다.

struct TREE
{
	int Idx;
	int x;
	int y;
	TREE *Left;
	TREE *Right;
};

 

#2. 입력 데이터 관리

입력 데이터로는 문제에서 주어진 Node들이 번호 순서대로 좌표로 주어지게 된다.

즉 ! 우리는 이 입력데이터만을 보고는 어떤 Node가 어떤 Node의 부모Node인지, 자식노드인지, 왼쪽자식인지, 오른쪽 자식인지 알 수가 없다. 따라서 이 입력 데이터를 알아볼 수 있게 정리하는 과정이 필요하다.

이를 위해서 본인은 #1에서 정의해놓은 구조체를 자료형으로 갖는 vector를 하나 선언해 주었다.

그리고, 이 입력데이터들을 vector에 삽입 후, vector를 정렬하는 방식으로 정리해 주었다.

즉 ! 다음과 같이 먼저, Vector에 입력 데이터들을 삽입해 주었다.

	vector<TREE> Tree;
	for (int i = 0; i < nodeinfo.size(); i++)
	{
		int x = nodeinfo[i][0];
		int y = nodeinfo[i][1];
		int Idx = i + 1;
		Tree.push_back({ Idx, x, y, NULL, NULL });
	}

그리고 이 Vector를 정렬을 시켜 주었는데, 어떻게 정렬을 하면 좋을지 생각을 해보자.

Tree에서 가장 중요한 것은, Root Node가 될 것이다. 그럼 Root Node는 어떤 특징을 가지고 있는지 알아보자.

Root Node는 "주어진 Node들 중에서, y좌표 값이 가장 큰 Node" 가 된다.

즉 ! Node들끼리 비교를 해서 정렬을 할 때, 첫  번째 우선순위는, "y좌표값이 더 큰지 작은지" 가 될 것이다.

그 다음 우선순위는 어떻게 될까 ?? 바로 "x좌표"가 될 것이다. x좌표가 상대적으로 더 작다면, Left Child Node가 될 것이고 그게 아니라면 Right Child Node가 될 것이다. 이를 x좌표의 순서대로 정렬을 시켜 주었다.

즉 ! 위와 같은 그림이 주어졌을 때, Vector에 삽입 후 정렬을 시켰다면 Vector에는 다음과 같은 순서대로 Node들이 저장되어 있을 것이다.

[ 7 , 4 , 2 , 6 , 1 , 3 , 9 , 8 , 5 ]

가장 Root Node부터 상대적으로 높이가 더 높은 Node들을 우선적으로, 그리고 같은 높이일 경우에는 x좌표가 더 작은  Node들 순으로 정렬을 시켜준 것이다. 이와 같이 정렬을 시켰다면 이제 우리는 이를 바탕으로 Tree를 만들 수 있다.

 

#3. Tree만들기

이를 바탕으로 Tree를 본격적으로 만들어 보자.

역시나, 가장 기준이 되는 Node는 Root Node가 될 것이다. 그런데 ! Root Node는 어디에 저장되어 있을까 ??

바로 #2에서 정렬시켜놓은 Vector의 0번 Index에 저장되어 있다. 우리는 이렇게 Root Node를 쉽게 찾을 수 있다.

이 Root Node를 기준으로 나머지 Node들의 위치를 파악해보자.

 

#Case1

 

첫 번째 Case를 살펴보자. 빨강색 Node가 현재 기준이 되는 Node이고, 파랑색 Node가 현재 위치를 찾고자 하는 Node라고 생각해보자. 파랑색 Node가 빨강색 Node의 Left Child에 위치한다는 것을 눈으로 보고는 알 수 있지만, 이를 우리가 가진 정보로는 어떻게 파악할 수 있을까 ?? 바로 "x좌표"를 통해서 파악을 할 수가 있다.

"빨강색 Node의 x좌표 > 파랑색 Node의 x좌표" 인 경우, 이 파랑색 Node는 빨강색 Node의 Left Child라고 판단할 수 있다.

그럼 ! 파랑색 Node를 삽입했다고 가정한 채로, 다음 Case로 넘어가보자.

 

#Case2

이 경우를 살펴보자. Case1에서 빨강색과 파랑색을 삽입을 한 후, 이어서 초록색 Node를 삽입하려고 한다.

그럼 ! 가장 먼저 Root Node인 빨강색 Node와 초록색 Node의 x좌표를 비교할 것이다.

당연히, 빨강색 Node의 x좌표가 초록색 Node의 x좌표보다 더 크기 때문에, 초록색 Node는 빨강색 Node의 Left Child에 속하는 Node라는 것을 알 수 있다. 그럼 Case1에서 진행한 것과 같이 그대로 빨강색 Node의 Left Child Node로 삽입을 해버리면 될까 ??? 눈으로 보고 있어서 알겠지만, 이는 잘못된 삽입이다. 왜냐하면 이미 파랑색 Node가 빨강색 Node의 Left Child에 자리잡고 있기 때문이다.

그럼 ! "빨강색 Node의 Left Child로 파랑색, 초록색 Node 2개가 올 수도 있지 않을까?" 라고 생각할 수 있지만, 그럴수가 없다. 왜냐하면 이 문제에서 주어진 트리는 "이진트리(Binary Tree)" 라고 했기 때문이다. "이진트리"는 자식이 딱 2개인 Tree를 의미한다. 즉 ! Node 하나 당 가질 수 있는 최대 자식의 수가 2개 이고, Left에 1개, Right에 1개를 가질 수 있는 Tree가 이진트리이기 때문에, 절대로 ! 초록색 Node가 파랑색 Node와 형제 Node같은 역할을 함과 동시에, 빨강색 Node의 Left Child로써의 역할을 수행할 수 없다는 것이다.

그럼 ! 이 경우에는 어떻게 해야 할까 ?? 이미 파랑색 Node가 Left Child로 자리잡고 있으면, 초록색 Node는 어떻게 될까 ??

기준점을 파랑색 Node로 바꿔주면 된다.

처음에는 빨강색 Node가 Root Node인지라 기준점으로 잡고, 빨강색 Node vs 초록색 Node로 비교를 했지만, 이 과정에서 파랑색 Node의 존재를 알게 되었으므로, 이제는 기준을 파랑색 Node로 잡아주면 된다.

파랑색 Node와 초록색 Node의 x좌표를 비교해보면, 파랑색 Node가 더 크고, 파랑색 Node의 Left Child Node가 비어있으므로 ! 초록색 Node의 자리는 파랑색 Node의 Left Child가 되는 것이다.

 

위의 Case1, 2에서 왼쪽 자식을 삽입하는 경우에 대해서 이야기를 했지만, 오른쪽 자식을 삽입할 때에도 똑같은 논리가 적용이 된다. 다를 것이 하나도 없다. 문제는 ! 이를 코드로 구현하는 것인데, 재귀를 이용하면 간단하게 구현할 수 있다.

재귀로 구현할 때 필요한 정보는 딱 2가지이다.

1. 기준이 되는 Node

2. 현재 자리를 찾는 Node

이 2가지 Node가 필요하니, 이 2개를 인자로 갖는 재귀함수를 구현하면 된다. 코드는 다음과 같다.

void Make_Binary_Tree(TREE *Root, TREE* Child)
{
    if (Root->x > Child->x)
    {
        if (Root->Left == NULL)
        {
            Root->Left = Child;
            return;
        }
        Make_Binary_Tree(Root->Left, Child);
    }
    else
    {
        if (Root->Right == NULL)
        {
            Root->Right = Child;
            return;
        }
        Make_Binary_Tree(Root->Right, Child);
    }
}

line3 ~ 10)은 Left Child일 경우, 그 이후의 코드는 Right Child일 경우이다.

line3)에서 가장 Root Node의 x좌표와, 현재 삽입하려는 Node의 x좌표를 비교하고 있다.

line5)에서 아직 Left Node가 없는 경우 그대로 삽입을 하는 것을 볼 수 있다.

line10)은 "이미 Left Node가 있는 경우"를 표현한 것이다. 이 경우에는, Case2에서 기준 Node를 빨강색에서 파랑색 Node로 옮겼듯이, 기준이 되는 Node를 바꿔서 재귀를 호출하는 것을 확인할 수 있다.

이 이후의 코드는 Right Child일 경우 똑같이 적용되는 것을 구현한 것이다.

 

이로써 우리는 주어진 입력 데이터들을 하나의 Tree로 만드는 것을 완성했다.

이제 본격적으로 전위 , 후위 순회에 대해서 알아보자./

 

#4. 전위순회

먼저 간단하게 전위순회가 무엇인지에 대해서 부터 알아보고 가자.

전위순회는 Tree를 탐색하는 순서 중에 하나인데, 그 순서가 부모Node - Left Node - Right Node 순으로 탐색을 하게 된다.

위와 같은 Tree가 있을 때, 전위 순회는 다음과 같다.

[ 1 - 2 - 4 - 8 - 5 - 9 - 3 - 6 - 10 - 7 ]

이 순서에 대해서 이야기를 해보자면, 다음과 같다.

1. 가장 큰 부모 Node인 Root Node '1'번 Node를 탐색한다.

2. '1'의 Left Node인 '2'를 탐색한다.

3. 2의 과정에서 탐색한 '2'는 '1'의 Left Child인 동시에 또 다른 SubTree의 Root Node가 되기 때문에

    여기서 '부모 - Left - Right' 라는 전위순회 방식이 다시 적용된다.

4. 과정 3에 의해서 '2'의 Left Child인 '4'를 방문한다.

5. 과정 3과 같은 이유로 '4'는 또 다른 SubTree의 RootNode이므로 '부모 - Left - Right' 방식이 다시 적용된다.

6. 과정 5에 의해서 '4'의 Left Child인 '8'을 방문한다.

7. '8'번 Node 이후에 또 다른 Node는 없으므로 이 Node의 부모 Node인 '4'로 가서 Right Child를 탐색해본다.

8. '4'의 Right Child는 없으므로 탐색을 중단하고 이 Node의 부모 Node인 '2'로 돌아가서 Right Child를 탐색해본다.

9. '2'의 Right Child인 '5'번 Node를 탐색한다.

10. 과정 3과 같은 이유로, '5'는 또 다른 Root Node이므로 '부모 - Left - Right' 방식이 다시 적용된다.

11. '9'를 탐색 후, 더 이상의 탐색 Node가 없음을 확인하고 부모인 '5', '5'의 부모인 '2', '2'의 부모인 '1'까지 다시 돌아간다.

12. '1'의 Left Child를 모두 탐색했으므로 '1'의 Right Child를 탐색한다.

13. Right Child도 위와 같은 방식으로 탐색을 하면 3 - 6 - 10 - 7 이라는 순서로 탐색을 진행하게 된다.

 

이를 코드로 구현할 때에는 재귀를 사용하게 되는데 코드는 다음과 같다.

void PreOrder(TREE *Root, vector<int> &answer)
{
    if (Root == NULL) return;
    answer.push_back(Root->Idx);
    PreOrder(Root->Left, answer);
    PreOrder(Root->Right, answer);
}

매개변수로 호출되어 지고 있는 'Root'는 "현재 탐색하고 있는 Node"를 의미한다.

line4)에서 보면 "현재 Node를 탐색했습니다" 라고 표시해주기 위해서 answer에 삽입해 주는 과정이다.

line5)는 현재 Node를 탐색 후, Left Child를 탐색하기 위한 호출 과정이다.

line6)은 Left Child를 모두 탐색 후 , Right Child를 탐색하기 위한 호출 과정이다.

 

#5. 후위순회

후위순회 또한 Tree의 탐색하는 방법 중 하나이다. 그 순서가 Left - Right - 부모 순서로 탐색을 진행하게 된다.

위와 같은 Tree가 존재할 때 후위순회의 탐색 순서는 다음과 같다.

[ 8 - 4 - 9 - 5 - 2 - 10 - 6 - 7 - 3 - 1 ]

이 순서에 대해서 이야기를 해보자면 다음과 같다.

1. 가장 먼저, Left Child를 탐색하기 위해서 Root Node인 '1'의 Left Child인 '2'로 넘어간다.

2. '2'의 Left Child인 '4', '4'의 Left Child인 '8' 까지 넘어간다.

3. '8'의 Left Child는 존재하지 않으므로 '8'을 탐색한다.

4. 이 후, '8'이 후에는 더 이상의 Node가 존재하지 않으므로 이 Node의 부모 Node인 '4'의 Right Child를 찾아본다.

5. '4'의 Right Child는 없으므로 Right Child 다음 목표인 부모 노드인 '4'를 탐색한다.

6. '4'를 Root Node로 하는 Sub Tree를 모두 탐색하였으니, '4'의 부모 Node인 '2'의 Right Child를 탐색한다.

7. '2'의 Right Child인 '5', '5'의 Right Child인 '9'를 탐색한다.

8. '9' 이후에 또 다른 Node가 없으므로 '5'를 탐색한다.

9. '2'를 Root Node로 하는 Sub Tree의 Right Child를 모두 탐색하였으니, 이제 부모인 '2'를 탐색한다.

10. '1'을 Root Node로 하는 Tree의 Left Child를 모두 탐색하였으니, Right Child로 넘어간다.

11. 위와 같은 원리로 '1'의 Right Child를 후위순회로 탐색하면 10 - 6 - 7 - 3 - 1 이 된다.

 

이를 코드로 나타내면 다음과 같다.

void PostOrder(TREE *Root, vector<int> &answer)
{
    if (Root == NULL) return;
    PostOrder(Root->Left, answer);
    PostOrder(Root->Right, answer);
    answer.push_back(Root->Idx);
}

 

이와 같은 방식으로 이 문제를 해결할 수 있다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
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)
    {
        if (A.y == B.y)
        {
            if (A.x < B.x)
            {
                return true;
            }
            return false;
        }
        return true;
    }
    return false;
}
 
void Make_Binary_Tree(TREE *Root, TREE* Child)
{
    if (Root->x > Child->x)
    {
        if (Root->Left == NULL)
        {
            Root->Left = Child;
            return;
        }
        Make_Binary_Tree(Root->Left, Child);
    }
    else
    {
        if (Root->Right == NULL)
        {
            Root->Right = Child;
            return;
        }
        Make_Binary_Tree(Root->Right, Child);
    }
}
 
void PreOrder(TREE *Root, vector<int> &answer)
{
    if (Root == NULL) return;
    answer.push_back(Root->Idx);
    PreOrder(Root->Left, answer);
    PreOrder(Root->Right, answer);
}
 
void PostOrder(TREE *Root, vector<int> &answer)
{
    if (Root == NULL) return;
    PostOrder(Root->Left, answer);
    PostOrder(Root->Right, answer);
    answer.push_back(Root->Idx);
}
 
vector<vector<int>> solution(vector<vector<int>> nodeinfo) 
{
    vector<vector<int>> answer;
    vector<TREE> Tree;
    for (int i = 0; i < nodeinfo.size(); i++)
    {
        int x = nodeinfo[i][0];
        int y = nodeinfo[i][1];
        int Idx = i + 1;
        Tree.push_back({ Idx, x, y, NULL, NULL });
    }
    sort(Tree.begin(), Tree.end(), Cmp);
    TREE *Root = &Tree[0];
    for (int i = 1; i < Tree.size(); i++) Make_Binary_Tree(Root, &Tree[i]);
    vector<int> Pre_V; PreOrder(Root, Pre_V);
    vector<int> Post_V;    PostOrder(Root, Post_V);
    answer.push_back(Pre_V);
    answer.push_back(Post_V);
    return answer;
}