[코드테스트]우선탐색(깊이/너비)_DFS/BFS

DFS 와 BFS 이란

 

미뤄두었던 DFS 와 BFS에 대해 공부해 보자.

DFS(Depth First Search)는 깊이 우선탐색, BFS(Breath First Search) 너비 우선탐색의 약자로 

DFS/BFS를 뭉뚱거려서 그래프 탐색 알고리즘이라고도 말한다. 의미를 하나씩 파혜 해보면

그래프 탐색 알고리즘:

• 그래프: 여러 개체들이 연결되어 있는 자료구조
• 탐색: 그래프 자료구조에서 특정개체 A를 찾을 때 사용하는 알고리즘이라 탐색으로 정의한다. 

문제유형

 

코드테스트에서 DFS/BFS로 풀 수 있는 문제유형은 대표적으로 3가지로 요약된다. 

• 경로탐색: A지점~B지점까지 가는데 최단거리 구하기, 최소시간 구하기 와 같은 경로탐색형 문제
• 네트워크유형:
  • 여러 개체가 주어지고 연결되어있는 그룹의 갯수를 구하는 문제
  • 2개의 개체가 같은 그룹에서 연결되어 있는지 확인하는 문제
• 조합 만들기: 여러가지 조합을 모두 만들고 비교해봐야 하는 조합형문제

내가 자주 이용하는 Programers 에서 타켓넘버, 네트워크, 단어 변환, 여행경로 문제들이 보이면

바로 직관적으로 DFS/BFS를 떠올려야 올바른 문제 해결방법으로 접근할 수 있다. 

 

구현방법

 

DFS는 한놈만 끝까지 팬다

DFS는 여러놈을 동시에 팬다

DFS구현을 위한 전제조건으로 재귀함수 구현이 필요하고

BFS구현을 위한 전제조건으로 Queue / Linked List의 이해와 구현이 필요하다. 

 

DFS/BFS중 어떤걸 선택할까 

 

나 같은 코린이 수준에서는 DFS알고리즘이 오류 디버깅이 쉽기 때문에 DFS를 BFS보다 더 선호한다. 

 

DFS는 순차적으로 하나의 조합을 완성하여 정답과 비교하고, 또 다른 조합을 만들어 정답을 비교해 나가기 때문에

어디서 부터 잘못 구동되는지 따라가서 분석하기가 BFS보다 훨씬 쉽다.

 

BFS는 한 번에 여러조합을 병렬적 생성하다보니 조합이 완성되어 정답과 비교시점에 정답과 다르다면 
일상에서도 병렬처리가 안되는 나로서는 대략 디버깅시 어려움이 극심하거나 디버깅이 불가하거나 하였다. 

 

아무래도 멀티태스킹 병렬처리가 안되는 나의 성격상 DFS가 더 편하게 느껴질 수 밖에 없음을 몸으로 체험하였다.

그래서 개인적으로 DFS를 선호하지만 문제가 복잡할 때  DFS는 모든 케이스를 탐색하다보니 시간복잡도에서 BFS대비 

극히 불리한 경우가 생길 수 있음을 미리 알려 둔다. 

시간 복잡도 측면에서는 BFS가 훨씬 유리한 고급알고리즘 이지만 일단은 DFS로 버텨보는 것으로 하겠다.