프로그래머스 문제를 풀다보면, 간혹 이진트리를 만들어 풀어야하는 경우가 있다. 깊이우선 탐색, 너비우선 탐색, 힙 정렬 등이 있다.

(힙 같은 경우 배열로 할 수 있다.)

갑자기 이진트리를 만드려고 하니, 순간 머리가 멍해지는 느낌이 있어서, 아무래도 한번쯤 정리해야겠다는 생각을 하게 됐다.

 

struct Node{
    int value = 0;
    Node* left = nullptr;
    Node* right = nullptr;
    Node* parent = nullptr;    
};

 

 우선 노드는 위와 같다. 왼쪽, 오른쪽 그리고 부모를 가르키는 포인터를 두었다.(사실 부모를 가르키는 것은 안둬도 된다.)

 

 

void addNode(queue<Node*>& add_queue, int value)
{
    //큐에서 노드를 꺼낸다.(제거하지 않고 꺼낸다.)
    Node* node = add_queue.front();
    if(node->left == nullptr)
    {
        //왼쪽이 비었을 경우,
        node->left = new Node();
        node->left->value = value;
        node->left->parent = node;
        add_queue.push(node->left);
    }
    else
    {
        //오른쪽이 비었을 경우,
        node->right = new Node();
        node->right->value = value;
        node->right->parent = node;
        add_queue.push(node->right);
    }
    
    //왼쪽 오른쪽이 모두 가득 찬 경우, 큐에서 제거한다.
    if(node->left != nullptr && node->right != nullptr)
        add_queue.pop();
}

 알고리즘 문제에서, 완전 이진트리로 만드는 경우가 많은데, 그 경우 큐를 활용 해야 한다. 큐에 생성한 노드를 넣고, 새 노드를 추가 할 때,

큐에 추가한 순서대로, 자식 노드가 비었는지 확인 후 넣으면 된다. (너비우선 탐색할 때도, 큐를 이용하면 된다.)

 

//make bianry tree
queue<Node*> add_queue;    
Node* root = new Node();    
add_queue.push(root);

int i = 1;
int add_count = 0;
for(auto& num : numbers)
{
    add_count = pow(2,i++);
    for(int j = 0 ; j < add_count ; j++)
        addNode(add_queue, j%2 == 0 ? num : -num);
}

 

 위 코드는 프로그래머스 문제 해결 중, 트리를 만드는 과정의 코드이다. 루트 노드를 하나 만들고, 그 후, 노드들을 추가했다.

 

void search(Node* node)
{
    //노드 값 출력
    printf("%d", node->value);
    if(node->left == nullptr && node->right == nullptr)
    {
		//가장자리 노드에 왔을 때,
    }
    else        
    {
        //재귀적으로 왼쪽 탐색
        search(node->left, sum+node->value, target);
        
        //재귀적으로 오른쪽 탐색
        search(node->right, sum+node->value, target);
    }
}

 

 위 코드로 깊이 우선 탐색(DFS) 해, 값을 출력하도록 했다. 너비우선탐색(BFS)는 재귀적으로 동작하지 않는다. 큐를 이용해, 방문했던 노드를 넣고, 순서대로 동작시켜야 한다.

'게임을 만들자 > C++' 카테고리의 다른 글

[알고리즘] 이진트리 만들기  (1) 2021.05.22
c++11 min, max 범위, 난수 생성  (1) 2020.04.07
c++ string tokenizer  (0) 2015.01.09
cJSON parsing error using window utf-8 txt file, Remove UTF-8 BOM  (0) 2015.01.08
c++ Easing code  (0) 2014.10.16
c++ Builder 패턴  (0) 2014.04.16
이세계 용병 온라인

댓글을 달아 주세요

  1. 물약부장

    관리자의 승인을 기다리고 있는 댓글입니다