[코딩테스트] 2-3. 깊이/너비 우선 탐색(DFS/BFS)

그래프 탐색 알고리즘 중에 DFS, BFS가 존재

 

배경지식

1. 그래프(graphs)

여러 개체들이 연결되어 있는 자료 구조

- 정점(vertex, node)과 간선(edge, link)

- 유향(directed)그래프와 무향(undirected)그래프

2. 스택(stack)

3. 큐(queue)

 

* 추가로 알아야할 것

중복을 허용하지 않는 집합 : unordered_set

[key, value]로 순서 없이 자료 보관 : unordered_map  (내부적으로 hash 구조)

<-> map : 자동으로 정렬되는 컨테이너 (내부적으로 tree 구조)

 

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

한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하되, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점으로 진행

<노드 방문 순서>

0 -> 1 -> 3 -> 7 -> 5 -> 2 -> 6

 

*스택, 재귀함수를 이용하여 어느 정점에서 DFS를 하고 있는지를 기억하고 되돌아감

 

 

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

한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하고,

방문한 각 인접 정점을 기준으로 (방문한 순서에 따라) 또다시 너비 우선 탐색을 행함

<노드 방문 순서>

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

 

*큐, LinkedList를 이용하여 어느 정점에서 BFS를 해야하는지를 기록하고 진행함

 

 

DFS? BFS? 뭘 써야하지?

DFS를 선호하지만 BFS로 풀어야할 때가 있다.

둘 다 탐색하는 알고리즘이라 정답은 다 나온다.

그렇지만, DFS는 동작 검증하기가 쉽다.

왜냐하면 하나의 조합을 완성해서 정답 비교 후 또다른 조합 만들며 정답 비교 식으로 반복한다.즉, 정답을 비교하는 시점에 조합이 잘 나왔는지 확인하기가 빠르고 쉽다 !

그에 비해, BFS는 한번에 여러 조합들을 한칸 한칸씩 만들다 보니

조합 완성되어 정답과 비교하는 시점에 언제 어떻게 이렇게 만들어졌지?

어디서 틀렸지?를 분석하기 까다롭다.

그러나, DFS는 한놈만 패는데 한놈이 너무 오래 걸리면 시간 초과될 수 있다.

 

DFS는 수행시간 관점에서 복불복.

그에 비해, BFS는 모든 경우의 수를 한걸음씩 나가기 때문에

초반에 느려보일 수 있지만 하나의 정답만 찾고 나면

나머지 경우의 수는 정답에서 제외된다. = 대박날 확률도, 쪽박날 확률도 적다 = 시간복잡도가 낮다

 

 

대표적인 문제 유형

1. 경로탐색 유형(최단거리, 최소시간)
2. 네트워크 유형(연결되어 있는 그룹의 개수 구하기, 개체가 같은 네트워크에 속해있는지 확인 할 때)
3. 조합 유형 (모든 조합 만들기)