[알고리즘] 깊이/너비 우선 탐색 DFS/BFS

그래프 탐색 알고리즘 DFS / BFS

그래프 : 여러 개체들(node)이 간선(edge)로 연결되어 있는 자료구조

탐색 : 특정 개체를 찾기 위한 알고리즘. 

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

* 그래프와 트리의 차이? 

간단하게 말하자면 그래프 중에서 방향성이 있는 비순환 그래프를 트리라고 한다. 

 

대표적 문제 유형

1. 경로 탐색 유형 (최단거리, 시간)

2. 네트워크 유형 (연결)

연결되어 있는 그룹의 갯수 구하기 or 두 개체가 같은 네트워크 속에서 연결되어 있는지 확인

3. 조합 유형 (모든 조합 만들기) 

여러가지 조합 모두 만들고 비교 

ex) 프로그래머스 타겟넘버, 네트워크, 단어변환, 여행경로 등 

 

깊이 우선 탐색 (DFS, Depth-First Search)

: 최대한 깊이 내려간 뒤, 더이상 갈 곳이 없을 경우 옆으로 이동

루트 노드에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식. 

 

너비 우선 탐색 (BFS, Breadth-First Search)

: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

루트 노드에서 시작해 인접 노드를 먼저 탐색하는 방식.

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택. 

 

 

구현 방법

DFS - 재귀함수가 일반적

재귀 함수를 타고 타고 탈출조건에 먼저 도달하고 파라미터를 하나씩 바꿔가며 정답을 찾아가는 방식 

BFS - Queue / LinkedList 를 사용하는 것이 보편적. 

턴을 돌면서 가장 먼저 넣었던 것을 꺼내, 연결된 점을 Queue에 넣기. Queue가 빌 때까지 반복

순서가 보장되어야 하기 때문에 큐나 링크드리스트를 사용 

 

DFS 장점 - 검증이 쉽다. 재귀함수만 익혀두면 코드도 훨씬 간결. 버그 발생 가능성이 비교적 낮다. 

DFS 단점 - 수행 시간이 복불복. 한놈이 너무 오래 걸리면 시간이 초과될 수 있다. 

BFS 장점 - 시간복잡도가 낮다(?) 

 

코딩테스트 tip) 

둘 다 탐색을 하는 알고리즘이기 때문에 어떤 걸 써도 정답은 나오지만 상황에 따라 적합한 것을 사용.

1. 단순히 그래프의 모든 정점을 방문하는 것이 중요한 문제는 DFS, BFS 중 어느 것을 사용해도 무방. 편한것으로.

2. 경로의 특징을 저장해둬야 하는 문제는 DFS를 사용. (경로에 조건이 있거나...)

3. 미로 찾기 등 최단거리 구해야 하는 문제는 BFS가 유리. 가장 먼저 찾아지는 해답이 곧 최단거리이기 때문.  

* 앞쪽 쉬운 문제로 출제시 빠르게 DFS로 풀고, 뒤쪽 어려운 문제로 출제시 시간초과 방지를 위해 BFS로 푸는 것을 추천. 

 

 

참고 : youtube_개발자로 취직하기,