[C++ 자료구조] STL deque 사용 예제

지난 포스팅에서 STL deque을 사용하면, stack과 queue를 구현할 수 있고

 

element access 할 수 있어, STL stack, queue 를 사용할 때보다 편리한 점이 있다고 소개했었다.

 

이번 시간에는 해당 예제를 살펴보도록 하겠다.

 

---

 

아래와 같은 map이 있다고 하자.

 

우리가 알고자 하는 것은 (0, 0)에서 (6, 5)로 가는 모든 경로와 최소 거리이다.

 

int map[7][7] = {
    { 1, 0, 0, 0, 0, 1, 0},
    { 1, 1, 0, 0, 0, 1, 0},
    { 0, 1, 1, 1, 1, 1, 0},
    { 0, 1, 1, 0, 0, 1, 1},
    { 1, 1, 0, 0, 0, 1, 0},
    { 1, 0, 0, 0, 1, 1, 0},
    { 1, 0, 0, 0, 1, 1, 0},
};

 

 

경로를 구할 때는 dfs를 사용하여 구하면 된다.

 

다음은 recursive 기반의 dfs을 통해 도착점까지의 거리를 구한 예이다.

 

#include <iostream>
#include <deque>
 
using namespace std;
 
int map[7][7] = {
    { 1, 0, 0, 0, 0, 1, 0},
    { 1, 1, 0, 0, 0, 1, 0},
    { 0, 1, 1, 1, 1, 1, 0},
    { 0, 1, 1, 0, 0, 1, 1},
    { 1, 1, 0, 0, 0, 1, 0},
    { 1, 0, 0, 0, 1, 1, 0},
    { 1, 0, 0, 0, 1, 1, 0},
};
 
// print the number of way of (x1, y1) to (x2, y2) and the shortest path
 
#define PATH_NUM_MAX 10000
 
int target_x;
int target_y;
int path_index;
int path_num[PATH_NUM_MAX];
 
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
 
void dfs(int n, int cur_x, int cur_y)
{
    
    cout << "[" << path_index << "] " << "cur_pox: (" << cur_y << ", " << cur_x << ")" << endl; 
    
    if (cur_x == target_x && cur_y == target_y)
    {
        if (path_index + 1 >= PATH_NUM_MAX) 
        {
            cout << "error: out of PATH_NUM_MAX" << endl;
            return;
        }
        path_num[path_index++] = n;
        return;
    }
    
    map[cur_y][cur_x] = -1;
    
    for (int i=0; i<4; i++)
    {
        int next_x = cur_x + dx[i];
        int next_y = cur_y + dy[i];
        
        if (next_x >= 7 || next_x < 0 || next_y >= 7 || next_y < 0) continue;
        if (map[next_y][next_x] != 1) continue;
        
        dfs(n+1, next_x, next_y);
    }
    map[cur_y][cur_x] = 1;
 
}
 
int main()
{
    target_x = 5;
    target_y = 6;
    
    int start_x = 0;
    int start_y = 0;
    
    dfs(0, start_x, start_y);
    
    int min_path = 9999;
    for (int i=0; i<path_index; i++)
    {
        cout << "path count: " << path_num[i] << endl;
        if (min_path > path_num[i])
        {
            min_path = path_num[i];
        }
    }
    cout << "min: " << min_path << endl;
}

 

---

 

해당 코드를 실행시켜 보면, 최소 거리는 11로 나타나고 총 4가지 방법이 있다는 것을 알 수 있다.

 

4가지 path는 어떻게 표시하면 될까? 

 

위의 코드에서 stack 을 추가하여 다음(현재) 위치가 업데이트 될 때마다 push,

 

다음(현재) 위치에서 return 하여 현재(이전) 위치로 되돌아갈 때마다

 

(해당 경로가 목표지점으로 도달하는 경우가 아니라서) pop 하여 경로를 저장하면 될 것이다.

 

그리고 목표지점(target_x, target_y)에 도달 했을 때, stack 의 값을 print 하면 될 것이다.

 

#include <iostream>
#include <deque>

using namespace std;

int map[7][7] = {
    { 1, 0, 0, 0, 0, 1, 0},
    { 1, 1, 0, 0, 0, 1, 0},
    { 0, 1, 1, 1, 1, 1, 0},
    { 0, 1, 1, 0, 0, 1, 1},
    { 1, 1, 0, 0, 0, 1, 0},
    { 1, 0, 0, 0, 1, 1, 0},
    { 1, 0, 0, 0, 1, 1, 0},
};

// print the number of way of (x1, y1) to (x2, y2) and the shortest path

#define PATH_NUM_MAX 10000

int target_x;
int target_y;
int path_index;
int path_num[PATH_NUM_MAX];

deque<int> path_x_stack;
deque<int> path_y_stack;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

void dfs(int n, int cur_x, int cur_y)
{
    
    
    path_x_stack.push_back(cur_x);
    path_y_stack.push_back(cur_y);

    //cout << "[" << path_index << "] " << "cur_pox: (" << cur_y << ", " << cur_x << ")" << endl; 
    
    if (cur_x == target_x && cur_y == target_y)
    {
        if (path_index + 1 >= PATH_NUM_MAX) 
        {
            cout << "error: out of PATH_NUM_MAX" << endl;
            return;
        }
        path_num[path_index++] = n;
        
        cout << "[" << path_index << "] path: ";
        for (int i=0; i<path_x_stack.size();i++)
        {
            cout << "-> (" << path_y_stack[i] << ", " << path_x_stack[i] << ")";
        }
        cout << endl;
        
        path_x_stack.pop_back();
        path_y_stack.pop_back();
        return;
    }
    
    map[cur_y][cur_x] = -1;
    
    for (int i=0; i<4; i++)
    {
        int next_x = cur_x + dx[i];
        int next_y = cur_y + dy[i];
        
        if (next_x >= 7 || next_x < 0 || next_y >= 7 || next_y < 0) continue;
        if (map[next_y][next_x] != 1) continue;
        
        dfs(n+1, next_x, next_y);
    }
    map[cur_y][cur_x] = 1;

    path_x_stack.pop_back();
    path_y_stack.pop_back();
}

int main()
{
    target_x = 5;
    target_y = 6;
    
    int start_x = 0;
    int start_y = 0;
    
    dfs(0, start_x, start_y);
    
    int min_path = 9999;
    for (int i=0; i<path_index; i++)
    {
        if (min_path > path_num[i])
        {
            min_path = path_num[i];
        }
    }
    cout << "min: " << min_path << endl;
}