프로그래머스. 길 찾기 게임

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

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

 

이진트리를 구성하고, 전위 순회(preorder), 후위 순회(postorder)를 하는 문제였다.

사실 전위순회, 후위순회를 옛날에 학교에서 배웠는데 정확한 정의가 기억이 안나기도 하고 

이런식으로 트리를 구조체로 구성하고 순회하는 문제는 풀어본적이 없어서 다른 분들의 코드를 보고나서 풀었다.

 

트리 구성

노드를 표현할 구조체를 정의한다.

struct Node
{
    int num;
    int x, y;
    Node* left;
    Node* right;
};

연결리스트를 구성할때처럼 left child와 right child를 포인터로 가르키도록 해주면 된다.

트리를 구성하는 방법은 다른 분 코드에서 재귀를 이용해 깔끔하게 구성하는 방법이 있었다.

먼저 Node 구조체가 들어가는 벡터를 만들고 정렬해주는데 y기준 내림차순 정렬, y가 같다면 x기준 오름차순 정렬해준다. 

그리고 루트를 기준으로 하는 재귀함수를 만든다.

void MakeTree(Node *root, Node *child)
{
    // left child
    if(child->x < root->x)
    {
        // 현재 기준 루트의 left child가 아직 없으면 할당 후 리턴
        if(root->left == NULL)
        {
            root->left = child;
            return;
        }
        // 이미 있다면 기준 루트 변경
        MakeTree(root->left, child);
    }
    // right child
    else
    {
        if(root->right == NULL)
        {
            root->right = child;
            return;
        }
        MakeTree(root->right, child);
    }
}

함수를 보면 루트를 기준으로 child의 x값이 루트보다 왼쪽에 있으면 child가 left child가 된다.

그런데 만약 root의 left child가 이미 있다면 해당하는 left child를 루트로 하는 재귀함수를 호출한다.

right도 마찬가지다.

즉 첫 재귀에서 그래프의 루트 (가장 위에 있는 노드)에서부터 아래로 내려가면서 child의 자리를 찾는다. 

 

전위순회는 Parent -> Left child -> Right child 순으로 탐색한다. 

재귀를 이용해서 dfs 처럼 함수를 구성하면 아주 깔끔하게 짜여지는것을 볼 수 있다. 

// parent, left, right
vector<int> preorder;
void PreOrder(Node *root)
{
    if(root == NULL) return;

    preorder.push_back(root->num);
    PreOrder(root->left);
    PreOrder(root->right);
}

 

후위순회는 Left child -> Right child -> Parent 순으로 탐색한다.

마찬가지로 재귀를 이용하면 깔끔하다.

// left, right , parent
vector<int> postorder;
void PostOrder(Node *root)
{
    if(root == NULL) return;

    PostOrder(root->left);
    PostOrder(root->right);
    postorder.push_back(root->num);
}

 

 

 

---

2022.02.16