[알고리즘/프로그래머스] 길 찾기 게임 (Lv.3)

코테 스터디에서 공부한 문제로 프로그래머스의 길찾기게임 문제이다.

[ 문제풀이 ]

기본적인 문제 해석은 노드의 위치가 주어질 때 이진 트리를 완성하고 각 트리의 전위 순회, 후위 순회를 진행하면 되는 문제였다.

전위 순회, 후위 순회의 경우 재귀적으로 해결하면 어렵지 않은 알고리즘이지만, 이 문제의 경우 주어진 노드들을 연결하여 트리를 완성하는 것이 관건인 문제였다.트리를 완성하는 단계는 아래에 설명으로 표시하겠다.

#1. TREE 구성

기본적으로 트리를 작성하기 위해 TREE라는 구조체를 새로 정의할 수 있어야 하는 문제였다.문제에서는 주어진 노드들의 좌표와 문제에서 설명된 이진 트리의 특성을 통해 이진 트리를 완성하기만 하면 쉬운 문제다.

 

먼저 Tree의 경우 필요한 변수들을 생각해보았다.

1. 트리 내 해당 노드의 (x , y)좌표 정보가 필요할 것이다.(이건 기본적으로 문제에서 주어지는 것이다.)

2. 해당 노드의 번호가 필요할 것이다.(문제에서 전위 순회, 후위 순회를 진행하여야 하기 때문에 필요한 노드의 번호가 필요하다.)

3. 각 노드에서 연결되는 왼쪽 자식 노드, 오른쪽 자식 노드가 어떻게 연결되어있는지 알아야 한다.

 

그래서 위의 정보를 멤버변수로 갖는 구조체를 하나 만들어 주었다.

 

struct TREE{
    int num;
    int x, y;
    TREE *leftNode;
    TREE *rightNode;
};

 

#2. 주어진 데이터를 활용하여 Root Node 찾기

주어진 입력 데이터는 각 노드의 x, y 좌표만 주어지는데 이를 활용하여 먼저 트리의 기본이 되는 루트 노드를 찾아야 했다.

이를 위해 모든 노드들을 하나의 벡터에 넣은 후 정렬을 해야 되겠다고 생각했다.그 이유는 이 노드들이 누구와 연결되어 있고, 부모 노드는 어떤 노드인지 알 수 없기 때문이었다.

 

1. 먼저 모든 노드들을 담을 수 있는 벡터를 선언하여 일단 다 넣어보았다.

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

 

이런 식으로 모든 노드들의 정보를 담고 있는 벡터를 만들었다.

 

2.  노드를 정렬하여 루트 노드를 찾아보자.

트리를 활용할 때 보통 트리의 기본이 되는 루트 노드를 찾는 것이 제일 먼저이기 때문에 문제에서 주어진 이진 트리의 성격을 통해 루트 노드를 찾으면 된다.

나는 그 방법들 중 하나로 루트 노드나 레벨이 낮은 노드의 경우 각 노드의 y좌표가 다른 노드보다 크다는 것을 활용하였다.

algorithm 헤더를 활용한 sort함수를 활용하여 노드를 원하는 방식으로 정렬하였다.

이때, 기본적으로 y값이 큰 노드를 먼저 앞으로 오게 하고, y값이 같은 노드의 경우 x좌표가 작은 순서대로 정렬해주었다.

bool cmp(TREE A, TREE B)
{
    if(A.y == B.y)
        return A.x < B.x;
    return A.y > B.y;
}

 

 

 

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

 

#3. Tree만들기

정렬된 벡터를 활용해서 이제 트리를 완성하기만 하면 된다.이때 이진트리의 성질을 활용한다면 트리는 쉽게 만들 수 있다.이진 트리의 경우 자식이 되는 노드는 두개밖에 없기 때문에 기준이 되는 루트 노드부터 하나씩 이어주면 된다.

 

1.  연결하고 싶은 노드의 x값이 부모 노드의 x값 보다 작은 경우

만약 연결하고 싶은 노드의 x값이 부모 노드의 x값 보다 작은 경우에는 반드시 왼쪽 자식으로 들어가야한다.

이때 우리는 이미 y값을 기준으로 정렬을 했기 때문에 x값만을 기준으로 자식을 이어주면 된다.

쉽게 이야기하면 분기점이 두개밖에 더 생기지 않는 다는 이야기다.

 1 - 1. 부모 노드의 왼쪽 자식이 존재하지 않을 경우

 부모 노드의 왼쪽 자식이 존재하지 않을 경우 그냥 현재 연결하고 싶은 노드는 부모 노드의 왼쪽 자식 노드로 연결하면 된다.

 1 - 2. 부모 노드의 왼쪽 자식이 이미 존재할 경우

 부모 노드의 왼쪽 자식이 이미 존재할 경우, 부모 노드의 왼쪽 자식을 부모로 다시 판단하여 현재 연결할 노드를 연결하면 된다.

 

2.  연결하고 싶은 노드의 x값이 부모 노드보다 큰 경우  반대로 연결하고 싶은 노드의 x값이 부모 노드의 x값 보다 큰 경우에는 부모 노드의 오른쪽 자식으로 연결하면 된다.위와 똑같이 두가지 분기점밖에 생기지 않는다. 2 - 1. 부모 노드의 오른쪽 자식이 존재하지 않는 경우

 

 2 - 2. 부모 노드의 오른쪽 자식이 이미 존재할 경우 

 

 

그렇다면 이제 트리를 완성하기 위해서는 모든 준비가 끝난 것이다.

void MakeTree(TREE *root, TREE* node)
{
    if(root->x > node->x)
    {
        if(root->leftNode == NULL)
        {
            root->leftNode = node;
            return;
        }
        else
        {
            MakeTree(root->leftNode, node);
        }
    }
    else
    {
        if(root->rightNode == NULL)
        {
            root->rightNode = node;
            return;
        }
        else
        {
            MakeTree(root->rightNode, node);
        }
    }
}

 

이렇게 트리를 재귀적으로 완성하는 함수를 작성한 뒤 모든 노드와 root노드를 메소드에서 활용하면 된다.

아래의 코드는 solution 함수에서 트리를 만들기 위해 위의 함수를 사용하는 방법이다.

TREE *root = &treeV[0];
    
    for(int i=1; i<treeV.size(); i++)
    {
        MakeTree(root, &treeV[i]);
    }

이제 문제에서 원하는 트리의 구조를 모두 완성하였고 루트 노드를 알기 때문에 전위 순회와 후위 순회만 작성하면 된다.

 

 

#4. 전위순회 (재귀 사용)

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

따라서 코드에서 확인하면 부모 노드에서 방문 처리 후, 왼쪽 노드 방문, 오른쪽 노드 방문이라고 생각하면 된다.

 

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

void PreOrder(TREE* node)
{
    if(node == NULL)
        return;
    
    pre.push_back(node->num);
    PreOrder(node->leftNode);
    PreOrder(node->rightNode);
}​

 

#5. 후위순회 (재귀사용)

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

순회의 방법은 똑같지만 부모 노드의 방문 순서만 다르기 때문에 전위 순회를 했다면 매우 쉽게 후위 순회도 작성할 수 있다.

 

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

void PostOrder(TREE* node)
{
    if(node == NULL)
        return;
    PostOrder(node->leftNode);
    PostOrder(node->rightNode);
    post.push_back(node->num);
}

 

 

 

 

[ 전체 코드 ]

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

using namespace std;

vector<int> pre;
vector<int> post;

struct TREE{
    int num;
    int x, y;
    TREE *leftNode;
    TREE *rightNode;
};

bool cmp(TREE A, TREE B)
{
    if(A.y == B.y)
        return A.x < B.x;
    return A.y > B.y;
}
void MakeTree(TREE *root, TREE* node)
{
    if(root->x > node->x)
    {
        if(root->leftNode == NULL)
        {
            root->leftNode = node;
            return;
        }
        else
        {
            MakeTree(root->leftNode, node);
        }
    }
    else
    {
        if(root->rightNode == NULL)
        {
            root->rightNode = node;
            return;
        }
        else
        {
            MakeTree(root->rightNode, node);
        }
    }
}
void PreOrder(TREE* node)
{
    if(node == NULL)
        return;
    
    pre.push_back(node->num);
    PreOrder(node->leftNode);
    PreOrder(node->rightNode);
}

void PostOrder(TREE* node)
{
    if(node == NULL)
        return;
    PostOrder(node->leftNode);
    PostOrder(node->rightNode);
    post.push_back(node->num);
}
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    
    vector<TREE> treeV;
    for(int i=0; i<nodeinfo.size(); i++)
    {
        int x = nodeinfo[i][0];
        int y = nodeinfo[i][1];
        int num = i + 1;
        treeV.push_back({num, x, y, NULL, NULL});
    }
    
    sort(treeV.begin(), treeV.end(), cmp);
    
    TREE *root = &treeV[0];
    
    for(int i=1; i<treeV.size(); i++)
    {
        MakeTree(root, &treeV[i]);
    }
    PreOrder(root);
    PostOrder(root);
    answer.push_back(pre);
    answer.push_back(post);
    return answer;
}​

 

 

---

이 문제의 경우 문제의 개념은 그렇게 어렵지 않았지만 트리를 완성하는것이 문제의 핵심이었던 것 같다.

또한 트리의 성질을 잘 파악하여 루트 노드를 찾고 루트 노드부터 하나씩 트리를 완성하는 것이 중요했다.