CS/알고리즘
DFS, BFS
1. DFS(깊이 우선 탐색)DFS 정의 및 개념그래프나 트리에서 한 번에 가능한 한 깊은 노드까지 탐색을 진행한 뒤, 더 이상 갈 곳이 없으면 돌아가서 다른 경로를 탐색한다.자식 노드를 먼저 탐색하고, 자식 노드가 더 이상 없으면 부모 노드로 돌아가서 다른 자식 노드를 탐색한다.기본적으로 재귀적으로 구현한다.스택(Stack)을 이용하여 비재귀적으로도 구현한다. 동작 방식① 시작 노드를 방문하고 스택에 넣는다.② 스택에서 노드를 꺼내며, 그 노드와 연결된 인접 노드를 방문한다.③ 더 이상 방문할 노드가 없으면 스택에서 가장 최근에 방문했던 노드로 돌아가 다른 경로를 탐색한다.④ 이 과정을 더 이상 탐색할 노드가 없을 때까지 반복한다. 구현 방법1. 재귀적 구현재귀 호출을 사용하여 DFS를 구현한다...
2025. 1. 11.
