[Algorithm] BFS & DFS

BFS (Breadth First Search)

• 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘
• 루트 노드 (혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
• Queue를 이용하여 구현
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용
• 시간 복잡도 O(N)

BFS 진행 과정

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다.

2. 큐에서 원소를 꺼내서 해당 칸의 상하좌우로 인접한 칸에 대해 다음 3번을 진행한다.

3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 넣는다.

4. 큐가 빌 때까지 2번을 반복한다.

 

⇒ 모든 칸이 큐에 1번씩 들어가므로 시간 복잡도는 칸이 N개일 때 O(N)이다.

 

DFS (Depth First Search)

• 루트 노드 (혹은 다른 임의의 노드)에서 시작해서 다른 분기 (branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
• 재귀를 이용하여 구현
• 모든 노드를 방문하고자 하는 경우 사용
• 시간 복잡도 O(N)

DFS 진행 과정

1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남긴다.

2. 스택에서 원소를 꺼내서 해당 칸의 상하좌우로 인접한 칸에 대해 다음 3번을 진행한다.

3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 넣는다.

4. 스택이 빌 때까지 2번을 반복한다.

 

⇒ 모든 칸이 스택에 1번씩 들어가므로 시간 복잡도는 칸이 N개일 때 O(N)이다.

 

출처 바킹독 블로그