ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1260. DFS와 BFS ( Stack & Queue 사용 )
    알고리즘/백준 BAEK JOON 2020. 3. 10. 01:25

    이번에 풀어볼 문제는 백준 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형을 쓰자!! -> 디버깅할 때 편한거 같다.(개인차)

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    1874.스택 수열  (0) 2020.04.02
    11403.경로찾기  (0) 2020.03.16
    2178. 미로탐색  (0) 2020.03.15
    1260. DFS와 BFS ( Stack & Queue 사용 )  (0) 2020.03.10
    [백준] 퇴사 14501  (0) 2019.04.18
    [백준] 연구소 14502  (0) 2019.04.15

    댓글 0

Designed by Tistory.