-
코테 일기(7) : 백준 [1260번] DFS와 BFS(DFS & BFS 완성)프로그래밍/C++ 2020. 4. 20. 00:37반응형
오랜만에 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)을 풀어보겠다.
전체 코드는 댓글로 이메일 남겨주시면 보내드리겠습니다.
'프로그래밍 > C++' 카테고리의 다른 글
코테 일기(9) : 백준 [2178번] 미로찾기(BFS) (0) 2020.04.21 코테 일기(8) : 하노이탑(The tower of Hanoi) (0) 2020.04.20 코테 일기(6) : 백준 [1260번] DFS와 BFS(BFS편) (0) 2020.04.05 코테 일기(5) : CodeUp [1093] 이상한 출석 번호 부르기1 (0) 2020.04.05 코테 일기(4) : CodeUp [1090] 수 나열하기2 (0) 2020.04.05