1260. DFS와 BFS ( Stack & Queue 사용 )

이번에 풀어볼 문제는 백준 1260번 이며 완전탐색 알고리즘의 대표 DFS와 BFS이다. 

# 많은 블로그에서 해당 알고리즘에 대한 자세한 설명이 되어있으니 참고!!

 

나의 경우는 DFS의 경우 재귀함수를 사용해서 풀어도 되지만 굳이 Stack을 너무나 사용해서 풀고 싶었다.

알고리즘을 다시 시작한지 얼마안되서 꽤 오랜시간이 걸렸지만 그래도 해내서 다행이다:)

 

Stack과 Queue에 대한 개념과 DFS와 BFS의 탐색 과정을 생각하며 구현하면된다!

-> 구현을 외우는 것이 아니라 이해하는 것이 중요하고 예외처리를 잘 하는것이 가장 중요한 Point다!

 

 

< Code 설명 >

#include <iostream>
#include <stack>
#include <queue>

#define MAX 1001

using namespace std;

int n, m, v;
bool visit1[MAX];
bool visit2[MAX];
int arr[MAX][MAX];


//정점 개수 N, 간선 개수 M, 시작 정점 번호 V
void dfs(int v){
    stack<int>s;
    s.push(v);
    visit1[v]=true;
    cout << v << " ";
    while(!s.empty()){                // Stack이 텅 빌때까지 진행!
        for(int i=1; i<=n; i++){      // 시작정점부터 for문으로 순서대로 dfs탐색 진행
            if(visit1[i]==false){     // 방문한 정점인지 Check
                if(arr[v][i]==1){     // 정점사이에 간선이 존재하는지 Check
                s.push(i);            // 방문한 적이 없고 간선이 존재 -> 스택에 push
                    
                    visit1[i]=true;   // 방문한 정점은 True로 Check
                    
                    v = s.top();      // 스택의 최상위를 기준정점으로 초기화해서 탐색 
                                      // -> 해당 정점과 연결된 정점 탐색을 위해
                                      // -> 이런식으로 하면 정점 순서(낮은)대로 탐색가능
                   	
                    i=0;              // 최상위 정점과 연결된 정점들과 간선 탐색
                                      // 방문한 적이 없는 정점들 기준으로 간선이 있는지 
                                      // 최상위 정점과 연결된 간선이 있나 처음부터 탐색 
                                      // -> for문이므로 정점순서가 낮은 순서로 쌓이게됨
                                      // -> for 문의 i++ 주의해서 구현!!
                    
                    cout << v << ' '; // 스택 최상위 값 출력
                }
            }
        }
        // for 문이 끝났는 것 == 깊이 끝까지 탐색했다는 것, 이제 미탐색한 나머지를 찾아 방문
        if(visit1[v]==true){          // 만약 방문한적이 있다면
            s.pop();                  // 스택에서 pop해준다. 
                                      // -> 더 이상 탐색을 할 필요가 없는 정점이므로..
                                      // -> 더 이상 간선이 없으며 방문한적이 있는 경우
                                      
            if(!s.empty())            // 스택이 비어있지 않다면
                v = s.top();          // 거슬러 올라간 부분에서 재탐색하기위해
                                      // v값을 스택의 최상위 값으로 저장
        }
    }
    cout << endl;
}

void bfs(int v){
    queue <int>q;
    q.push(v);
    visit2[v]=true;
    cout << v << " ";
    while(!q.empty()){                             // Queue가 텅 빌때까지!
        for(int i=1; i<=n; i++){                   // 정점의 갯수만큼 반복한다.
            if(visit2[i]==false && arr[v][i]==1){  // 방문한적 없고 간선이 있다면
                q.push(i);                         // Queue에 넣는다.
                visit2[i]=true;                    // 방문 Check
                cout << i << " ";                  // 방문하자마자 출력한다!
            }
        }
        if(visit2[v]==true){                     // 제일 처음시작한 정점과 연결된
                                                 // 간선을 모두 방문했다면
                                                 
            q.pop();                             // 그 정점을 빼고 다음의 빠른순서의
                                                 // 정점부터 재탐색한다.
                                                   
            v=q.front();                         // Queue의 제일 앞에 있는 것이 
                                                 // 다음으로 빠른순서의 정점이 된다.
                                                 // 그 이유는 for문을 참조
        }
    }
}

int main() {
    cin >> n >> m >> v;
    int st, ed;
    for(int i=0; i<m; i++){
        cin >> st >> ed;
        arr[st][ed] = arr[ed][st] = 1;
    }
    dfs(v);
    bfs(v);
    return 0;
}

반드시 알아야할 TIP!!

# 항상 알고리즘을 짜기전에 히든 테스트 케이스를 염두해두고 스스로 설계할줄 알아야한다.

 

# 구현 후 : 히든 테스트케이스를 만들고 디버깅을 하면서 제대로 동작하는지 확인해야한다! 
            -> 히든 테스트 케이스가 시간을 단축시켜준다!!

 

# 그리고 되도록이면 Check할 배열은 bool형을 쓰자!! -> 디버깅할 때 편한거 같다.(개인차)