1260
-
코테 일기(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 arr) { int*..
-
코테 일기(6) : 백준 [1260번] DFS와 BFS(BFS편)프로그래밍/C++ 2020. 4. 5. 16:29
CodeUp으로 몸? 뇌?를 풀어줬으니, 이제 알고리즘의 꽃인 백준 온라인 저지로 입성하자. 처음 접한 문제는 DFS, BFS를 다루는 문제였다. 그래프 탐색 알고리즘은 알고리즘 필수 요소 중 하나이기 때문에 절대적으로 짚고 넘어가야 한다. BFS는 Breath-First Search 이다. 즉 depth를 한 단계씩 내려가면서 너비를 위주로 탐색하는 너비우선탐색이다. 예제 입력 2번과 같은 경우 3번에서 1, 4번을 먼저 방문 한 후에1번에서 2번, 4번에서 5번을 방문하는 결과가 나온다.즉 3 (1 4) (2 5) 와 같은 결과가 나와야 한다. 처음 든 생각 정점(Node)의 개수가 N이고 간선의 개수가 M이면 탐색은 M번이 이루어 져야 한다. { for(int i = 0; i> srt >> dst;..