코테 일기(7) : 백준 [1260번] DFS와 BFS(DFS & BFS 완성)

오랜만에 C++을 잡으려 하니 벌써부터 심장이 아프다..

내가 짠 BFS 코드를 보면서 DFS를 짜기에는 코딩실력이 아닌 Copy and Paste의 느낌이 강할 것 같아 과감하게 BFS를 보지 않고 풀어보았다.

처음 든 생각

먼저 DFS는 stack 구조가 매우 편해보였다. Depth로 탐색을 하기에 Terminal Node(최하위노드)를 제거하는 것

이 아니고, 탐색을 할 노드가 없으면 Tree를 거슬러 올라가야 한다는 점에서 Stack을 사용했다.

또한 백준에서는 함수마다 입력을 받는 것이 아니라, 주어진 입력을 통해 두 개의 함수를 모두 사용하는 것이기에 처음 필요한 입출력을 main에 넣었다.

코드(DFS만)

void dfs(int n, int m, int v, vector<vector<int> > arr) {

        int* check = new int[n] {0};

        stack<int> s;

        cout << v << " "; //첫 번째 노드를 출력

        s.push(v);

        check[v - 1] = 1;

        for (int i = 0; i < m; i++) { 

//branch의 갯수만큼 수행(방문 횟수)

                 for (int j = 0; j < n; j++) { 

 //node의 갯수만큼 수행(모든 노드를 탐색하는 횟수)

                        

                         if (s.size() == 0) {

                                 //stack의 크기가 0이면 모든 node를 탐색했으므로 탐색 종료

                                 break;

                         }

                         if (arr[s.top()-1][j] == 1 && check[j] == 0) {

                         //방문하지 않은 노드중에서 현재 위치에서 이동할 수 있는 노드가                             존재하는지 여부를 판단

 

                                 cout << j+1 << " "; //값 출력

                                 check[j] = 1;

                                 s.push(j+1); //해당하는 값 넣기

                                 break; //stack의 top이 바뀌었으므로 loop 빠져나가기

                         }

                         if (j == n - 1 && s.size() != 0) {

                                 s.pop(); 

 //더 이상 방문할 곳이 없으면 depth를 위로 한칸 올라가기

                         }

                 }

        }

        cout << endl;

}

DFS는 BFS에 비해 상대적으로 쉬웠다. 아무래도 stack, 난이도가 아닌 Coding의 경험의 문제인듯하다.

우연히 한 블로그를 본적이 있는데 그 블로그에서 했던 말이있다.

"문제를 보고나서 어떤 말인지 아는데 막상 코드를 짤 때는 머리가 백지가 된다"

"문제를 보고나서 어떻게 짜야 할지도 아는데, 코드 짜는 실력이 부족하다"

나는 이번 기회로 이 두가지의 스킬이 늘었던 것 같다. 

2주전에만 해도 BFS를 보며 쩔쩔 맸었는데 이번 DFS를 짜는데 1시간도 걸리지 않았다.

다음에는 과제로 나왔던 하노이탑(The tower of Hanoi)을 풀어보겠다.

전체 코드는 댓글로 이메일 남겨주시면 보내드리겠습니다.