BFS(너비우선탐색)와 DFS(깊이우선탐색)

알고리즘을 공부하다가 꼭! 알아야하는 너비우선탐색과 깊이우선탐색에 대해 알아보고자 한다.

자료구조-트리 포스트에서 가볍게 훑어보고 넘어갔었는데, 알고리즘 문제에 적용하기 위해서는 더 알아볼 필요가 있다.

특히나 검색하면서 마이구미님의 Hello World 블로그에 이 이론들을 어떻게 문제에 적용시켜 풀지 생각하는데 도움이 많이 됐다.

링크로 가기 👉 마이구미의 Hello World

 

그래프(Graph)

---

연결되어 있는 객체 간의 관계를 표현하는 자료 구조이며 비선형 자료구조이다. 정점(vertex)과 두 노드를 연결하는 간선(edge)으로 이루어져있다. 

부모-자식 관계라는 개념이 없으며 2개 이상의 경로가 가능하다. 계층이 없기 때문에 루트라는 개념도 존재하지 않는다. 또, 순환 구조일 수도 있고, 비순환 구조일 수 도있다.

ex) 지도, 지하철 노선도의 최단경로 구하기, 전기회로 소자들, 선수 과목 등  

 

 

그래프의 종류에는 무방향 그래프와 방향 그래프가 있다.

 

무방향 그래프와 방향 그래프

말 그대로 무방향 그래프는 정점들 사이간의 갈 수 있는 방향이 정해져있지 않기 때문에 만약 3 -> 4로 갈 수 있다면 4 -> 3도 가능하다는 뜻이다. 하지만 방향 그래프라면 4 -> 3로만 가능하지, 그 반대인 3 -> 4은 불가능하다.

 

그래프 표현

그래프는 인접행렬(Adjacency Matrix)나 인접리스트(Adjacency List)로 표현할 수 있다. 참고로 아래의 예시는 방향 그래프 기준이다.

 

인접행렬(Adjacency Matrix)

인접 행렬은 정점(V)가 N개 일때 N*N배열의 형태로 나타낼 수 있다.

출처: http://btechsmartclass.com/data_structures/graph-representations.html

인접행렬 Array[0,  1](A -> B) = 1 이다. 만약 무방향 그래프라면 Array[1, 0](B -> A) 도 1일 것이다. 하지만 예시로 든 그래프는 방향 그래프이기 때문에 B -> A는 불가능하므로 값이 0이다. 인접행렬의 값이 1이면 정점간의 간선이 존재하는 것이고, 0이라면 존재하지 않는다는 뜻이다. 만약 가중치가 있다면, 배열의 값을 w(가중치)로 표현하면 된다. 

 

인접리스트(Adjacency List)

인접리스트는 행렬 형식이 아닌 배열 형식으로 저장된다. 

출처: http://btechsmartclass.com/data_structures/graph-representations.html

Array[0]은 A에서 탐색할 수 있는 간선 B, C가 저장되어있고 Array[1]에는 B에서 탐색할 수 있는 간선 D, E가 저장되어있다.

 

인접행렬의 크기는 정점들이 얼마나 간선으로 연결되어 있는지 상관없이 무조건 정점의 개수 V * V으로 만들어지기 때문에 공간복잡도가 O(V^2)이다. 하지만 인접리스트는 필요한 만큼만 쓰기 때문에 O(V+E)가 된다. 따라서 인접행렬보다 인접리스트가 효율적이라고 할 수 있다.

 

너비우선탐색(BFS)과 깊이우선탐색(DFS)

---

 

너비우선탐색(Breadth First Search)

너비 우선탐색은 큐를 사용하며, 어떤 정점을 방문한 후, 그 정점에 연결된 다른 정점들을 큐에 줄을 세워가면서 순차적으로 방문하는데, 방문하지 않은 정점이 없을 때(더이상 큐에 남아있는 정점이 없어질 때) 까지 다른 모든 정점들에 대해서 똑같은 방식으로 탐색을 한다.

출처: https://algorithms.tutorialhorizon.com/breadth-first-searchtraversal-in-a-graph/

 

위의 움짤을 보면 큐에 먼저 들어온 정점이 먼저 디큐되고 그 정점과 연결된 정점들이 큐에 인큐 되는 FIFO방식을 볼 수 있다.

 

• 두 노드사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
• 큐를 이용하므로 선입선출(FIFO)의 방식으로 탐색한다.

 

깊이우선탐색(Depth First Search)

깊이 우선탐색에는 스택이나 재귀를 사용하며 어떤 정점에서 그 정점과 연결된 정점까지 계속해서 나아가다가 목표 정점를 찾지 못하면 다시 가장 가까운 정점으로 돌아와서 다른 경로를 택해서 다시 탐색을 한다. 여기서 다시 되돌아 오는 과정을 백트래킹(Backtracking)이라고 한다.

 

예를 들면, 미로를 탐색할때 한 방향으로 갈 수 있는 곳 까지 계속해서 나아가다가, 막힌 곳이 나타나면 다시 가장 가까운 갈림길이 있는 곳으로 되돌아와서 다른 길로 탐색을 진행하는 방법과 유사하다.

 

출처: https://www.codesdope.com/course/algorithms-dfs/

 

위의 움짤을 보면 다른 경로를 찾기 위해 백트래킹을 하는 과정에서 LIFO방식으로 탐색하는 것을 볼 수 있다. 

 

• DFS는 현재 탐색하고 있는 경로 상의 노드들만 기억하면 되기 때문에 BFS에 비해 저장공간의 수요가 비교적 적다.
• 스택을 이용하기 때문에 후입선출(LIFO)의 방식으로 탐색한다.
• 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 해가 없는 경로에 깊이 빠질 가능성이 있기 때문에 미리 지정한 임의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 빠져나와서 다음 경로를 탐색하게 할수도 있다.
• 목표에 이를 수 있는 경로가 다수일 때, DFS는 목표에 다다르면 탐색을 끝내버리기 때문에 얻어진 해가 최단 경로라는 보장이 없다.