요즘 코딩테스트가 대중화되면서 graph traversal 에 대한 문제가 많이 나오는것 같다. 좀 완벽히 이해 하고자 해본다.

graph와 tree traversal에 대한 간단한 내용은 [Algorithm] Graph & Tree 읽어보면 좋을듯하고 이글에서는 graph traversal에 대해 구체적으로 구현하고 응용해 보겠다.

 

문제

아래와 같은 미로가 존재하고 'S'에서 시작하여 'E'로 이동합니다.  "▒"은 벽으로 이동 할 수 없습니다.

 

사전 정의

다음의 설명들에 사용된 코드들은 아래와 공통 코드를 사용합니다. 

더보기

위치를 저장하기 위한 클래스

class location{
public:
    int x;
    int y;
    shared_ptr<location> prev;
public:
    location(int x, int y, shared_ptr<location> prev)
    : x(x), y(y), prev(prev) {}
};

 

map과 방문지 맵을 활용한 이동가능 여부 판단함수

bool moveable(vector<vector<int>> & map, vector<vector<int>> & visited, int x, int y){
    if(x < 0 || x > map[0].size()-1) return false;
    if(y < 0 || y > map.size()-1) return false;
    if(map[y][x] != 0) return false;
    if(visited[y][x] != 0) return false;
    
    return true;
}

 

main 함수

int main(int argc, const char * argv[]) {
    vector<vector<int>> map = {
        {0, 1, 0, 0, 0, 0, 0},
        {0, 1, 0, 1, 0, 1, 0},
        {0, 0, 0, 0, 0, 1, 0},
        {1, 1, 1, 1, 0, 1, 0},
        {1, 1, 1, 1, 0, 0, 0},
    };
    
    print_map("MAP", map);
    cout << endl;

    {
        cout << "<BFS BY QUEUE>" << endl << endl;
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        queue<shared_ptr<struct location>> q; bfs(map, visited, q);
    }
    cout << endl;
    {
        cout << "<DFS BY STACK> " << endl;
        stack<shared_ptr<struct location>> s;
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        dfs(map, visited, s);
    }
    cout << endl;
    {
        cout << "<DFS BY RECURSIVE>" << endl;
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        dfs_recursive(map, visited, shared_ptr<location>(new location(0, 0, nullptr)));
    }
    cout << endl;
    {
        cout << "<DFS ALL BY RECURSIVE>" << endl;
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        vector<vector<int>> record(map.size(), vector<int>(map[0].size()));
        auto count = dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(0, 0, nullptr)));
        cout << "total path : " << count << endl << endl;
        
        print_visited("[VISITED]", map, record);
    }
    cout << endl;

    return 0;
}

 

결과 경로 및 방문지 출력 헬퍼 함수들

void print_map(const string & title, vector<vector<int>> & map){
    int width = (int)map[0].size();
    int height = (int)map.size();
        
    cout << "[" << title << "]" << endl;
    for(int x=0;x<width*2+1;x++)cout << "─"; cout << endl;
    for(int y=0;y<height;y++){
        cout << "│";
        for(int x=0;x<width;x++){
            string ch = " ";
            switch(map[y][x]) {
                case 1: ch  = "▒"; break;
                case 0: ch  = " "; break;
                case 9: ch  = "+"; break;
            }
            
            if(x == 0 && y == 0) ch = "S";
            else if(x == width-1 && y == height-1) ch = "E";
            
            cout << ch ;
            if(x != width-1)
                cout << " ";
        }
        cout << "│" << endl;
    }
    for(int x=0;x<width*2+1;x++)cout << "─"; cout << endl;
}

void print_visited(const string & title, vector<vector<int>> & map, vector<vector<int>> & visited){
    vector<vector<int>> visited_map = map;
    for(auto y=0;y<map.size();y++){
        for(auto x=0;x<map[0].size();x++){
            if(visited[y][x] == 1)
                visited_map[y][x] = 9;
        }
    }
    print_map(title, visited_map);
    cout << endl;
}

void print_result(vector<vector<int>> & map, vector<vector<int>> & visited, shared_ptr<location> & p, bool show_visited = true){
    vector<vector<int>> found_path = map;
        
    auto temp = p;
    while(temp != nullptr){
        found_path[temp->y][temp->x] = 9;
        temp = temp->prev;
    }
    print_map("PATH", found_path);
    
    
    if(show_visited) print_visited("VISITED", map, visited);
}

 

DFS (Depth First Search)

DFS는 진행할수있는 노드부터 먼저 search하는 알고리즘입니다. 전문적으로하면 하위노드를 먼저 search 해 나간다는것이고 하위노드를 더이상 search 할수없을때 진행방향과 반대로 돌아와야 합니다. 그래서 stack을 사용합니다.

 

일단 코드를 한번 봅시다.

void dfs(vector<vector<int>> & map, vector<vector<int>> & visited, stack<shared_ptr<location>> & s){
    int width = (int)map[0].size();
    int height = (int)map.size();
    
    s.push(shared_ptr<location>(new location(0, 0, nullptr)));
    while(!s.empty()){
        auto p = s.top(); s.pop();
        
        int x = p->x, y = p->y;
        
        visited[y][x] = 1;
        
        if(x == width - 1 && y == height - 1){
            print_result(map, visited, p);
            return;
        }
        
        if(moveable(map, visited, x-1, y)) s.push(shared_ptr<location>(new location(x-1, y, p))); // left
        if(moveable(map, visited, x+1, y)) s.push(shared_ptr<location>(new location(x+1, y, p))); // right
        if(moveable(map, visited, x, y-1)) s.push(shared_ptr<location>(new location(x, y-1, p))); // up
        if(moveable(map, visited, x, y+1)) s.push(shared_ptr<location>(new location(x, y+1, p))); // down
        
    }
}

 

스택을 사용해서 깊이우선 탐색을 해보았습니다. 그런데 출력값이 이상합니다.

탐색결과 방문지

짧은 길을 놔두고 빙빙 돌아갔습니다.

 

"DFS는 계속 앞으로 파 나아가기 때문에 최적의 길을 찾아주지는 않는다"라는 걸 알 수 있습니다.

 

좀더 간단한 실험을 위해서 재귀적으로 바꿔보겠습니다. (stack을 사용하면 recursive로 바꿀 수 있다. Stack과 Recursive을 참조하세요.) 

void dfs_recursive(vector<vector<int>> & map, vector<vector<int>> & visited, shared_ptr<location> p){
    int width = (int)map[0].size();
    int height = (int)map.size();
    
    int x = p->x, y = p->y;
    
    visited[y][x] = 1;
    
    if(x == width - 1 && y == height - 1){
        print_result(map, visited, p);
        return;
    }
    
    
    if(moveable(map, visited, x-1, y))
        dfs_recursive(map, visited, shared_ptr<location>(new location(x-1, y, p))); // left
    if(moveable(map, visited, x+1, y))
        dfs_recursive(map, visited, shared_ptr<location>(new location(x+1, y, p))); // right
    if(moveable(map, visited, x, y-1))
        dfs_recursive(map, visited, shared_ptr<location>(new location(x, y-1, p))); // up
    if(moveable(map, visited, x, y+1))
        dfs_recursive(map, visited, shared_ptr<location>(new location(x, y+1, p))); // down
}

 

엇 근데 결과값이 다름니다.

탐색결과 방문지

 

stack형은 갈수있는 모든 경로에 대해 stack에 push하고 찾고 recursive는 stack에 현재를 push하고 바로 하위노드를 찾기 때문에 결과가 다를뿐 최적의 경로를 찾지 못하는것은 같네요.

 

결국은 DFS는 기본적으로 모든 node를 방문하지만 유일한 최적의 경로를 찾아주지는 못하는구나... 

 

DFS로 하나의 경로를 찾는건 의미 없구나... 그럼 DFS는 완전 탐색이지 그럼 모든 경로의 수를 구할수 있겠구나. 

stack에서 pop할때 현재 위치의 visited flag를 지우면 더이상 진행경로가 없을때 백트렉킹하여서 다른 경로를 계속 찾아서 모든 경로를 방문한다는걸 이용해서 S->E로 가는 모든 경로를 찾아 봅시다.

int dfs_recursive_all(vector<vector<int>> & map, vector<vector<int>> & visited, vector<vector<int>> & record, shared_ptr<location> p){
    int width = (int)map[0].size();
    int height = (int)map.size();
    
    int x = p->x, y = p->y;
    
    visited[y][x] = 1;
    record[y][x] = 1;
    
    int theWays = 0;
    if(x == width - 1 && y == height - 1){
        print_result(map, visited, p, false);
        theWays += 1;
    }
    
    if(moveable(map, visited, x-1, y))
        theWays += dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(x-1, y, p))); // left
    if(moveable(map, visited, x+1, y))
        theWays += dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(x+1, y, p))); // right
    if(moveable(map, visited, x, y-1))
        theWays += dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(x, y-1, p))); // up
    if(moveable(map, visited, x, y+1))
        theWays += dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(x, y+1, p))); // down


    visited[y][x] = 0;
    
    return theWays;
}

 

탐색결과 방문지


total path : 4

 

S->E로 가는 모든 경로를 찾았고 가능한 모든 노드를 방문했습니다.

 

BFS (Breadth First Search)

DFS는 모든 경로를 찾아주지만 유일한 최적의 경로를 찾지는 못합니다. BFS은 갈수있는 모든 경우들을 적어두고 순차적으로 한번씩 방문하는경우로 Queue를 사용합니다. 항상 처음에 최단경로를 찾아줍니다.

void bfs(vector<vector<int>> & map, vector<vector<int>> & visited, queue<shared_ptr<struct location>> & q){
    int width = (int)map[0].size();
    int height = (int)map.size();
    
    q.push(shared_ptr<location>(new location(0, 0, nullptr)));
    while(!q.empty()){
        auto p = q.front(); q.pop();
        
        int x = p->x, y = p->y;
        
        visited[y][x] = 1;

        if(x == width - 1 && y == height - 1){
            print_result(map, visited, p);
            return;
        }
        
        if(moveable(map, visited, x, y-1)) q.push(shared_ptr<location>(new location(x, y-1, p))); // up
        if(moveable(map, visited, x, y+1)) q.push(shared_ptr<location>(new location(x, y+1, p))); // down
        if(moveable(map, visited, x-1, y)) q.push(shared_ptr<location>(new location(x-1, y, p))); // left
        if(moveable(map, visited, x+1, y)) q.push(shared_ptr<location>(new location(x+1, y, p))); // right
    }
}

 

위의 코드를 실행해보면 left-right-up-down의 순서에 상관없이 최단거리를 찾아 줍니다.

탐색결과 방문지

최단 경로만큼 다른 노드를 방문했지만 유일한 최단 경로를 찾았습니다.

 

아래에 full source를 올려둡니다. 여러가지 테스트 해봅시다.

 

더보기 
//
//  main.cpp
//  path_finder
//
//  Created by Jack Kim on 2023/06/01.
//

#include <iostream>
#include <vector>
#include <iomanip>
#include <queue>
#include <string>
#include <ostream>
#include <stack>
using namespace std;


class location{
public:
    int x;
    int y;
    shared_ptr<location> prev;
public:
    location(int x, int y, shared_ptr<location> prev)
    : x(x), y(y), prev(prev) {}
};

void print_map(const string & title, vector<vector<int>> & map){
    int width = (int)map[0].size();
    int height = (int)map.size();
        
    cout << "[" << title << "]" << endl;
    for(int x=0;x<width*2+1;x++)cout << "─"; cout << endl;
    for(int y=0;y<height;y++){
        cout << "│";
        for(int x=0;x<width;x++){
            string ch = " ";
            switch(map[y][x]) {
                case 1: ch  = "▒"; break;
                case 0: ch  = " "; break;
                case 9: ch  = "+"; break;
            }
            
            if(x == 0 && y == 0) ch = "S";
            else if(x == width-1 && y == height-1) ch = "E";
            
            cout << ch ;
            if(x != width-1)
                cout << " ";
        }
        cout << "│" << endl;
    }
    for(int x=0;x<width*2+1;x++)cout << "─"; cout << endl;
}

void print_visited(const string & title, vector<vector<int>> & map, vector<vector<int>> & visited){
    vector<vector<int>> visited_map = map;
    for(auto y=0;y<map.size();y++){
        for(auto x=0;x<map[0].size();x++){
            if(visited[y][x] == 1)
                visited_map[y][x] = 9;
        }
    }
    print_map(title, visited_map);
    cout << endl;
}

void print_result(vector<vector<int>> & map, vector<vector<int>> & visited, shared_ptr<location> & p, bool show_visited = true){
    vector<vector<int>> found_path = map;
        
    auto temp = p;
    while(temp != nullptr){
        found_path[temp->y][temp->x] = 9;
        temp = temp->prev;
    }
    print_map("PATH", found_path);
    
    
    if(show_visited) print_visited("VISITED", map, visited);
}

bool moveable(vector<vector<int>> & map, vector<vector<int>> & visited, int x, int y){
    if(x < 0 || x > map[0].size()-1) return false;
    if(y < 0 || y > map.size()-1) return false;
    if(map[y][x] != 0) return false;
    if(visited[y][x] != 0) return false;
    
    return true;
}

void bfs(vector<vector<int>> & map, vector<vector<int>> & visited, queue<shared_ptr<struct location>> & q){
    int width = (int)map[0].size();
    int height = (int)map.size();
    
    q.push(shared_ptr<location>(new location(0, 0, nullptr)));
    while(!q.empty()){
        auto p = q.front(); q.pop();
        
        int x = p->x, y = p->y;
        
        visited[y][x] = 1;

        if(x == width - 1 && y == height - 1){
            print_result(map, visited, p);
            return;
        }
        
        if(moveable(map, visited, x, y-1)) q.push(shared_ptr<location>(new location(x, y-1, p))); // up
        if(moveable(map, visited, x, y+1)) q.push(shared_ptr<location>(new location(x, y+1, p))); // down
        if(moveable(map, visited, x-1, y)) q.push(shared_ptr<location>(new location(x-1, y, p))); // left
        if(moveable(map, visited, x+1, y)) q.push(shared_ptr<location>(new location(x+1, y, p))); // right
    }
}

void dfs(vector<vector<int>> & map, vector<vector<int>> & visited, stack<shared_ptr<location>> & s){
    int width = (int)map[0].size();
    int height = (int)map.size();
    
    s.push(shared_ptr<location>(new location(0, 0, nullptr)));
    while(!s.empty()){
        auto p = s.top(); s.pop();
        
        int x = p->x, y = p->y;
        
        visited[y][x] = 1;
        
        if(x == width - 1 && y == height - 1){
            print_result(map, visited, p);
            return;
        }
        
        if(moveable(map, visited, x-1, y)) s.push(shared_ptr<location>(new location(x-1, y, p))); // left
        if(moveable(map, visited, x+1, y)) s.push(shared_ptr<location>(new location(x+1, y, p))); // right
        if(moveable(map, visited, x, y-1)) s.push(shared_ptr<location>(new location(x, y-1, p))); // up
        if(moveable(map, visited, x, y+1)) s.push(shared_ptr<location>(new location(x, y+1, p))); // down
        
    }
}

void dfs_recursive(vector<vector<int>> & map, vector<vector<int>> & visited, shared_ptr<location> p){
    int width = (int)map[0].size();
    int height = (int)map.size();
    
    int x = p->x, y = p->y;
    
    visited[y][x] = 1;
    
    if(x == width - 1 && y == height - 1){
        print_result(map, visited, p);
        return;
    }
    
    
    if(moveable(map, visited, x-1, y))
        dfs_recursive(map, visited, shared_ptr<location>(new location(x-1, y, p))); // left
    if(moveable(map, visited, x+1, y))
        dfs_recursive(map, visited, shared_ptr<location>(new location(x+1, y, p))); // right
    if(moveable(map, visited, x, y-1))
        dfs_recursive(map, visited, shared_ptr<location>(new location(x, y-1, p))); // up
    if(moveable(map, visited, x, y+1))
        dfs_recursive(map, visited, shared_ptr<location>(new location(x, y+1, p))); // down
}

int dfs_recursive_all(vector<vector<int>> & map, vector<vector<int>> & visited, vector<vector<int>> & record, shared_ptr<location> p){
    int width = (int)map[0].size();
    int height = (int)map.size();
    
    int x = p->x, y = p->y;
    
    visited[y][x] = 1;
    record[y][x] = 1;
    
    int theWays = 0;
    if(x == width - 1 && y == height - 1){
        print_result(map, visited, p, false);
        theWays += 1;
    }
    
    if(moveable(map, visited, x-1, y))
        theWays += dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(x-1, y, p))); // left
    if(moveable(map, visited, x+1, y))
        theWays += dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(x+1, y, p))); // right
    if(moveable(map, visited, x, y-1))
        theWays += dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(x, y-1, p))); // up
    if(moveable(map, visited, x, y+1))
        theWays += dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(x, y+1, p))); // down


    visited[y][x] = 0;
    
    return theWays;
}


int main(int argc, const char * argv[]) {
    vector<vector<int>> map = {
        {0, 1, 0, 0, 0, 0, 0},
        {0, 1, 0, 1, 0, 1, 0},
        {0, 0, 0, 0, 0, 1, 0},
        {1, 1, 1, 1, 0, 1, 0},
        {1, 1, 1, 1, 0, 0, 0},
    };
    
    print_map("MAP", map);
    cout << endl;

    {
        cout << "<BFS BY QUEUE>" << endl << endl;
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        queue<shared_ptr<struct location>> q; bfs(map, visited, q);
    }
    cout << endl;
    {
        cout << "<DFS BY STACK> " << endl;
        stack<shared_ptr<struct location>> s;
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        dfs(map, visited, s);
    }
    cout << endl;
    {
        cout << "<DFS BY RECURSIVE>" << endl;
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        dfs_recursive(map, visited, shared_ptr<location>(new location(0, 0, nullptr)));
    }
    cout << endl;
    {
        cout << "<DFS ALL BY RECURSIVE>" << endl;
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        vector<vector<int>> record(map.size(), vector<int>(map[0].size()));
        auto count = dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(0, 0, nullptr)));
        cout << "total path : " << count << endl << endl;
        
        print_visited("[VISITED]", map, record);
    }
    cout << endl;

    return 0;
}

'programming' 카테고리의 다른 글

[Algorithm] C++ 중복문자열 찾기  (0) 2023.06.04
[Algorithm] C++ 문자열 조합 (combination)  (2) 2023.06.04
[Algorithm] Graph & Tree  (0) 2023.05.30
[Algorithm] Stack 과 Recursive  (3) 2023.05.30
퍼포먼스 개선 - 디스크입출력(2006년 version)  (0) 2023.03.22

+ Recent posts

티스토리툴바