알고리즘 - 깊이우선탐색(DFS), 너비우선탐색(BFS)

⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

 

1-1. 깊이우선탐색(DFS)란?

그래프의 탐색 방법중 하나. Depth-First Search

 

연결된 것들을 최대한 깊게 내려가고 더이상 못내려가면 옆으로 이동하는 탐색방식.

이게 뭔소리냐. A가 BCD랑 연결되어있다고 생각하자. 

A에서 B와 연결되어있다는것이 확인되는 순간 바로 B로 이동한다.

그 후 B와 연결되어있는것을 파악하고 계속 이동하다가 더이상 연결된게 없다고 판단되면 C로 이동한다.

 

Ex) 시작점 -> 연결된 값들

기본 설정

A -> BCD

B -> EF

C -> K

D -> Q

 

진행 순서

A - B - E - F - C - K - D - Q

 

좀더 자세히 나타내면

A - B - C - 더이상 C에서 연결된게 없으므로 B로 백트래킹 - D - 더이상 D에서 연결된게 없으므로 B로 백트래킹 - 더이상 B에서 연결된게 없으므로 A로 백트래킹 - C - K - 더이상 K에서 연결된게 없으므로 C로 백트래킹 - 더이상 C에서 연결된게 없으므로 A로 백트래킹 - D - Q

 

이렇듯 하나의 방향으로 쭉 진행하다가 더이상 진행할 수 없을경우 전단계로 돌아와서 다음 타겟으로 이동하는 방식이다.

 

1-2. 너비우선탐색(BFS)란?

그래프의 탐색 방법중 하나. Breadth-First Search

 

연결된 것들을 최대한 넓게 이동하고 더이상 못움직이면 아래로 내려가는 탐색 방식.

이게 뭔소리냐. A가 BCD랑 연결되어있다고 생각하자.

A에서 BCD가 연결되어 있다는것을 파악하면 큐에 BCD를 넣는다.

그 후 큐에서 하나씩 값을 빼며 해당 값에 연결된 것을 탐색하고 존재한다면 큐에 넣는다. 

 

Ex) 시작점 -> 연결된 값들

기본 설정

A -> BCD

B -> EF

C -> K

D -> Q

 

진행 순서

A - B - C - D - E - F - K - Q

 

좀 더 자세히 나타내면

A (BCD를 스택에 넣음) - B(EF를 스택에 넣음) - C(K를 스택에 넣음) - D(Q를 스택에 넣음) - E - F - K - Q

 

출처 : https://yunyoung1819.tistory.com/86

2. 그럼 어떤 상황에서 DFS와 BFS를 사용하나?

그래프를 탐색할때 주로 사용한다. 그리고 둘다 시간 복잡도는 동일하다. 

그러면 왜 굳이 방법이 두개일까? 어느때 어느걸 써야 할까?

 

1) 그래프의 모든 정점을 방문이 목적

둘 중 편한 것을 사용하면 된다. 똑 같 다.

​

2) 경로의 특징을 저장해야 하는 문제

각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용해야한다.

왜 ? BFS는 특징을 못파악하거든.

 

3) 최단거리 문제

최단거리는 BFS가 유리하다. 

DFS는 처음으로 나오는 답이 최단거리가 아닐 수 있지만, 
BFS는 가까운 곳부터 찾기 때문에 제일 먼저 나오는 답이 최단거리다.

 

 

3. 어떻게 사용하나?

DFS는 밑으로 계속해서 진행하기 때문에 재귀, 스택을 활용해서 해결한다.

BFS는 가까운것 부터 탐색하기 때문에 큐를 활용한다.

 

4. 핵심 기술 : 재귀, 스택 / 큐

DFS와 BFS를 구현하는 기술이다. 활용 방법은 아래 Example에서 다루겠다.

 

5. Example

https://naemamdaelo.tistory.com/38

[Java] 백준 1260번 : DFS와 BFS

 

 

-꿑-