그래프 탐색 알고리즘 DFS/BFS 차이점 및 특징

그래프 탐색 알고리즘 이해하기

• 그래프: 여러 개체들이 연결되어 있는 자료구조
• 탐색: 특정 개체를 찾기 위한 알고리즘

 

DFS, BFS를 드라마를 볼 때로 비유하자면

• 드라마 한 개를 끝나길 기다렸다가 몰아본다 = DFS (깊이 우선 탐색)
• 드라마 여러 개를 하나씩 다 챙겨본다 = BFS (너비 우선 탐색)

 

---

대표적 문제 유형

   1. 경로 탐색 유형
     A 지점부터 B 지점까지의 최소 거리 구하기, 최단 시간 구하기

   2. 네트워크 유형
     여러 개체들이 주어진 상태에서 연결되어 있는 그룹의 개수 구하기,
     두 개체가 같은 네트워크 안에서 연결되어 있는지 확인하기

   3. 조합 유형
      여러 가지의 조합을 전부 만들고 비교해보기

 
프로그래머스의 타겟 넘버, 네트워크, 단어 변환, 여행경로 등의 문제를 보고 DFS/BFS 를 떠올렸다면?
=> 올바른 접근 방향!
 
 

구현 방법

DFS
- 한 놈만 끝까지 패는 유형
- 재귀함수가 가장 일반적
- 재귀를 타고 타고 타서 탈출 조건에 먼저 도달하고 그 다음에 파라미터를 하나씩 바꿔가면서 정답을 찾는 방식으로 구현
 
BFS
- 여러 놈을 한 대씩 때리면서 가는 유형
- Queue / Linked List 를 사용하는 것이 보편적 (순서가 보장되어야 하기 때문)
- 턴을 돌면서 1. 가장 먼저 넣었던 것부터 하나씩 꺼내서 2. 현재 노드에 연결된 점을 하나씩 Queue에 넣고 3. 다음 턴이 돼서 가장 먼저 넣었던 것을 또 꺼냄 4. 이것을 반복
 
 

DFS / BFS 중 어떤 걸 써야할까?

둘 다 탐색을 하는 알고리즘이므로 어떤걸 써도 정답은 나옴. 따라서 본인이 자신 있고 익숙한 알고리즘을 쓰는 것이 좋다. 
 
DFS

• 하나의 조합을 완성해서 정답과 비교하고, 또 다른 조합을 만들고 정답과 비교하는 식으로 동작
  • 정답과 비교하는 시점에 내가 기대한 대로 조합이 잘 나왔는지 확인하기가 쉽고 빠름
  • 짧은 시간 내에 알고리즘을 검증해야 하는 코딩 테스트에서 유리
• 재귀함수만 익혀두면 코드의 간결성 증가, 버그 발생 가능성 감소
• 수행 시간 관점에서는 복불복
  • 한 놈만 패는데 그 한 놈이 너무 오래 걸리면 시간 초과 위험 
  • 운이 좋으면 첫 번째 조합이 최적의 답이 되고, 최악의 경우에는 모든 조합을 다 만들어보면서 시간을 낭비할 수 있음

 
BFS

• 한 번에 여러 조합들을 한 칸씩 만드는 식으로 동작
  •  정답과 비교하는 시점에 '언제 어디서부터 만들어졌는지', '어디서부터 틀린 건지' 분석하기 까다로움
• 모든 경우의 수를 한걸음씩 나아가는 방식
  • 초반에는 느려보일 수 있지만 하나의 정답만 찾고 나면 나머지 대부분의 경우의 수는 정답에서 제외
  • 대박날 확률도 적지만 쪽발 칠 확률도 적다 (= 시간복잡도가 낮다)

 
대부분은 코딩테스트 TC(Test Case)들은 극악무도한 게 꼭 하나씩 들어가므로, 너무 단순하게 생각하면 시간초과로 실패하도록 설계되어 있음.
=> 앞쪽의 쉬운 문제들 중에서 DFS/BFS 유형이 나왔다면 빠르게 DFS로,
     뒤쪽의 난이도 있는 문제거나 DFS로 풀기에는 너무 오래 걸릴 것 같다면 BFS로 푸는 것을 추천!

---

** 각각의 탐색 알고리즘이 유리한 경우 정리

DFS가 유리한 경우: 
- 재귀적인 특징과 백트래킹을 이용하여 모든 경우를 하나씩 전부 탐색하는 경우
- Graph의 크기가 클 경우
- Optimal한 답을 찾는 것이 아닌 경우
- 경로의 특징을 저장해야 하는 경우 ex) 경로의 가중치, 이동 과정에서의 제약

BFS가 유리한 경우: 
- 최단 거리 or 최단 횟수 구하는 경우
- Optimal한 답을 찾는 경우 -> BFS는 가장 처음 발견되는 해답이 최단 거리이다!
- 탐색의 횟수를 구해야 하는 경우 (#7576 토마토 문제)