BFS1 DFS, BFS [Algorithm #1] 완전 탐색 방법이란, 모든 경우의 수를 따지는 것을 말한다. 단순한 편이고, 코테 현장에서 쉽게 떠올릴 수 있는 방법이다. 복잡도와 표본 수를 고려해야 하지만 대충 1억 회 이하는 충분히 사용이 가능하다고 한다. 완전 탐색 방법에는 크게 두 가지가 있다. 1. DFS (Depth First Search) : 깊이 우선 탐색 시작 지점에서 가장 깊이 있는 노드를 우선 탐색하는 방식. Stack을 이용하여 해결한다. pop했을 때 방문하지 않은 인접 노드가 있으면 그 노드를 push한다. 다시 pop할 때 방금 push했던 노드가 무조건 먼저 pop되므로 가장 깊은 노드를 향해 탐색하게 된다. 재귀(Recursion)와 for문을 이용하여 작은 정점부터 깊이 우선 탐색을 수행하게 된다. # 재귀를 이용한 D.. 2022. 7. 22. 이전 1 다음 728x90
