[알고리즘] Graph 방문 알고리즘 BFS, DFS

 

---

1. 그래프(Graph)란?

그래프란 정점과 선으로 이루어진 자료구조입니다. 더 자세한 내용은 아래 링크를 클릭해주세요. 

https://geukggom.tistory.com/8

[자료구조] Graph란?

 

- 그래프 탐색 : 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

---

2. BFS, DFS란?

• BFS : Breadth-First Search = 너비 우선 탐색. 인접한 노드를 먼저 탐색하는 방법.
• DFS : Depth-First Search = 깊이 우선 탐색. 한 노드에서 시작해서 해당 분기를 완벽하게 탐색한 후 다음 분기로 넘어가는 방법. 

BFS와 DFS의 차이점을 간단하게 그림으로 알아보자면 이렇습니다.

그림 출처 :  https://namu.wiki/w/BFS

---

< BFS(너비 우선 탐색) >

- 루트 노드(혹은 임의의 노드)에서 인접한 노드를 먼저 탐색하는 방법.

- 두 노드 사이의 최단 경로 또는 임의의 경로를 찾고 싶을 때 이 방법을 사용.

- 재귀적(자기 자신을 호출)으로 동작하지 않음. 

- 선입선출(FIFO) 원칙으로 탐색. 따라서 차례로 노드를 저장한 후 꺼낼 수 있는 자료 구조인 Queue를 사용함.

- 깊이가 1인 모든 노드를 방문한 후, 다음은 깊이가 2인 노드를, 그 다음은 깊이가 3인 모든 노드를 방문하는 식으로 진행하며, 방문할 곳이 없으면 탐색을 마친다. 최단 경로의 경우, 깊이가 가장 짧아 방문할 곳이 없는 경로를 탐색하면 탐색을 마친다. 

 

• 장점
  1. 최단 경로를 빠르게 찾을 수 있음.
• 단점
  1. 경로가 매우 길 경우, 탐색할 가지 수가 급격히 증가함에 따라 많은 기억 공간을 필요로 함.
  2. 경로가 존재하지 않는 비연결 그래프일 경우, 모든 그래프를 탐색한 후 실패로 끝남.
• 문제풀이 예시 : 게임 맵 최단거리

 

 

< DFS(깊이 우선 탐색) >

- 루트 노드(혹은 임의의 노드)에서 시작해서 해당 분기를 완벽하게 탐색한 후, 다음 분기로 넘어감.

- 모든 노드를 방문하고자 할 때 이 방법을 사용함. 

- 재귀적으로 동작하는 순환 알고리즘의 형태를 지님.

- 가중치가 있는 등 이동 과정에 여러 제약이 있을 경우 이 방법을 사용.

 

• 장점
  1. 현 경로상의 노드를 기억하기 때문에 적은 메모리 사용.
  2. 찾으려는 노드가 깊은 단계에 있는 경우, BFS보다 빠름.
• 단점
  1. 경로가 존재하지 않아도 끝날 때까지 탐색함.
  2. 최단 경로를 찾을 수 없음.

• 문제풀이 예시 : 타겟넘버