프로그래머스: 미로 탈출 명령어 - 실수 축제 (그래프 탐색에서 DFS와 BFS의 사용 )

아래 세가지 이유에 대해 알아보자. 

 

- 그래프 탐색에서 DFS와 BFS 차이점

- DFS: 스택, BFS:큐를 사용하는 이유 

- 각 기법을 언제 사용하는지 

 

## DFS와 스택 

dfs는 그래프 탐색 시 "한 방향으로 끝까지 탐색하고, 더이상 갈 곳이 없으면 되돌아와서 다른 경로를 탐색하는" 방법이다.

이 방법은 재귀적인 탐색을 요구한다. 

### 스택을 사용하는 이유 

- LIFO(Last In First Out) : 스택은 마지막에 삽입된 요소를 가장 먼저 꺼내는 자료구조다. 

dfs에서는 가장 최근에 발견된 노드를 먼저 탐색해야 하기 때문에, 노드를 탐색하면서 경로를 쌓아두었다가 더이상 갈 곳이 없을 때 되돌아가는데 적합하다. 

 

 

dfs에서 A 에서 출발해서 E를 찾는 과정을 살펴보자. 

1. A에서 출발하여 B로 이동, 스택: [A] → [A, B]
2. B에서 D로 이동, 스택: [A, B] → [A, B, D]
3. D에서 더 이상 갈 곳이 없으므로 B로 되돌아가서 C로 이동, 스택: [A, B] → [A] → [A, C]
4. C에서 E로 이동, 스택: [A, C] → [A, C, E]

결국 경로는 A -> C -> E가 된다. 

## BFS와 큐 

BFS는 그래프 탐색 시 "모든 인접한 노드를 먼저 탐색한 후, 그 다음 레벨의 노드로 이동하는" 방법이다. BFS는 노드를 탐색할 때, 먼저 발견된 경로를 우선적으로 처리하기 때문에 최단 경로를 찾는데 유리하다. 

### 큐를 사용하는 이유 

- FIFO(First In First Out) : 큐는 먼저 삽입된 요소를 가장 먼저 꺼내는 자료구조다. bfs에서는 가장 먼저 발견된 노드를 먼저 탐색해야 하므로, 큐에 추가된 순서대로 노드를 탐색해 나가는 것이 적합하다. 

 

 

BFS로 A에서 출발하여 E를 찾는 과정을 살펴보자. 

1. A에서 출발하여 B, C를 큐에 추가, 큐: [B, C]
2. B에서 D를 큐에 추가, 큐: [C, D]
3. C에서 E를 큐에 추가, 큐: [D, E]
4. D는 목표가 아니므로, 큐에서 꺼내고 다음 노드인 E를 탐색하여 목표에 도달

## DFS와 BFS의 사용 사례 

### DFS 사용 시기 

- 모든 경로를 탐색해야 하는 경우 

: 예를 들어, 미로의 모든 길을 찾거나, 모든 가능성을 탐색해야 할 때 사용한다. 

- 경로가 깊고, 목표가 먼 곳에 있을 가능성이 큰 경우 

: dfs는 빠르게 깊이 탐색할 수 있으므로 유리하다. 

- 백트래킹 문제 

: 경로를 추적하면서 조건에 맞지 않으면 되돌아가야 하는 경우 dfs가 적합하다. 

### BFS 사용 시기 

- 최단 경로를 찾아야 하는 경우 

: bfs는 레벨 순으로 탐색하기 때문에, 첫번째로 목표에 도달하는 경로가 최단 경로다. 

- 그래프가 넓고, 목표가 가까운 곳에 있을 가능성이 큰 경우 

: bfs는 넓게 탐색하여 목표를 빠르게 찾는다. 

- 최단 거리 문제 

: 예를 들어, 각 간선의 비용이 동일한 그래프에서 최단 경로를 구할 때 적합하다. 

## 요약 

 

• DFS는 스택을 사용하여 한 경로를 끝까지 탐색하고, 더 이상 갈 곳이 없으면 되돌아오는 방식으로 작동한다. 깊이 있는 탐색이 필요한 경우에 유리하다. 
• BFS는 큐를 사용하여 먼저 발견된 경로를 탐색하는 방식으로, 최단 경로를 찾는 데 유리하다.