[알고리즘] 깊이/너비 우선 탐색(DFS&BFS)
깊이 우선 탐색 (DFS, Depth-First Search)
- DFS는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
- DFS는
스택 자료구조 혹은 재귀함수를 이용한다.
- Stack: 먼저 들어온 데이터가 나중에 나가는
선입후출 형식의 자료구조. (입구와 출구가 하나인 형태)
- Recursive Function(재귀함수): 자기자신을 다시 호출하는 함수를 말한다.
- DFS의 동작 과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 더이상 위의 과정을 수행할 수 없을 때까지 반복한다.
너비 우선 탐색 (BFS, Breadth-First Search)
- BFS는 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
- BFS는
큐 자료구조를 이용한다.
- Queue: 먼저 들어온 데이터가 먼저 나가는
선입선출 형식의 자료구조이다. (입구와 출구가 모두 뚫려있는 터널 형태)
- BFS의 동작 과정
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
- 더이상 위의 과정을 수행할 수 없을 때까지 반복한다.
- 인접한 노드가 여러 개 일 수 있는데, 이때 어떤 노드부터 방문할 지를 결정하는 기준은 문제에서 요구하는 내용에 따라 달라질 수 있다.
- 다음은 그림 예제이다.
