Computer Science/Algorithm
[Python] 너비 우선 탐색(BFS, Breadth-First Search), 깊이 우선 탐색(DFS, Depth Frist Search)
핵심 개념DFS(Depth-First Search, 깊이 우선 탐색)와 BFS(Breadth-First Search, 너비 우선 탐색)는 그래프 탐색 알고리즘이다. DFS는 한 방향으로 끝까지 탐색한 후 돌아오는 방식이며, BFS는 가까운 노드부터 탐색하는 방식이다. 시간 복잡도두 탐색 방법의 시간 복잡도는 일반적으로 \( O(V + E) \)이다. 여기서 \( V \)는 vertex(or 노드) 개수, \( E \)는 edge(간선) 개수이다. DFS와 BFS 모두 모든 노드를 방문하기 때문에 그래프의 크기에 따라 탐색 시간이 결정된다. 동작방식 & 구현 DFS시작 노드에서 한 방향으로 갈 수 있는 만큼 탐색한다.더 이상 이동할 곳이 없으면 이전 노드로 돌아가 다른 경로를 탐색한다.모든 노드를 방문할..
