[알고리즘] 그래프 탐색 - 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)

 

 

 

그래프 탐색

 

 

정점(Node, Vertex)과 간선(Edge)로 이루어진 그래프.

이 그래프를 탐색하는 방법에는 대표적으로 두 가지 방법이 있습니다.

깊이 우선 탐색(DFS, Depth-First Search)와 너비 우선 탐색(BFS, Breadth-First Search) 입니다.

물론 다른 그래프 탐색 알고리즘도 존재하나, 이 둘이 가장 유명한 방법이지 않을까 싶네요.

 

 

 

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

 

 

DFS는 깊이 우선이라는 이름처럼 깊이를 우선적으로 탐색합니다.

한 노드의 연결된 노드를 먼저 탐색한다는 의미죠.

 

 

 

 

해당 그래프를 DFS로 탐색한다면 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 순서로 탐색합니다.

한 노드를 탐색할 때, 해당 노드와 연결된 노드가 있을 경우 추가적으로 탐색한 뒤,

탐색할 노드가 더 이상 없으면 부모 노드로 이동하고, 또 다른 노드를 탐색하는 방법입니다.

즉, 한 경로를 끝까지 모두 탐색한 뒤, 더 이상 갈 길이 없을 경우 뒤돌아오는 방식이죠.

 

 

이는 미로를 왼쪽 혹은 오른쪽 벽을 대고 출구를 찾는 방법과 비슷한 원리입니다.

쭉 가다가 갈림길을 만나면 오른쪽으로, 또 다시 갈림길을 만나면 또 오른쪽으로,

막다른 길을 만나면 뒤돌아와서 (한 경로를 완전히 탐색)

갈림길을 만나면 오른쪽으로 (뒤돌아오기 전의 왼쪽 경로에 해당) 탐색해가며 출구를 찾는 것이죠.

 

 

 

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

BFS(Breadth - First Search)는 너비 우선 탐색입니다.

깊이 우선 탐색이 한 경로를 끝까지 간 뒤, 뒤돌아와 부모 노드의 다른 자식노드부터 탐색하는 방법이였다면,

BFS는 너비 우선으로, 한 노드에서 시작해 인접한 노드를 모두 찾은 다음,

더 이상 인접한 노드가 없을 때,

방금 전 탐색한 노드들과 인접한(자식 노드)를 찾는 방식입니다.

 

 

 

 

1번 노드에서 시작합니다.

 

 

 

1번 노드와 인접한 2, 3번 노드를 탐색합니다.

 

 

 

 

이후 2, 3번 노드와 인접한 노드(자식 노드)를 찾습니다.

2번 노드는 4, 5

3번 노드는 6, 7번 노드입니다.

노드의 방문 순서는 1 -> (2 -> 3) -> (4 -> 5 -> 6 -> 7)로,

너비를 우선적으로 탐색하는 방법입니다.

 

 

 

 

위 미로 찾기 문제를 BFS로 탐색했다면 위와 같이 나타낼 수 있겠네요.

시작점에서 출발하여 연결된 칸을 1칸씩 이동하며,

모든 연결된 칸을 탐색했다면 그 다음 칸을 탐색하는 방식입니다.

 

위와 같이 미로를 탐색하면 한 칸씩 전진하고 뒤로 가서 다른 경로를 가야되지 않냐구요?

컴퓨터의 세계니, 자신이 탐색했던 길에 한해 순간이동이 가능하다고 생각해봅시다 ㅎㅎ...

 

 

 

DFS vs BFS

미로탐색 : 최단경로 찾기

 

 

 

위 미로의 경우 DFS식 탐색 방법을 적용하여 오른쪽 벽에 손을 대고 길을 찾으면,

BFS보다 빠르게 찾을 수 있습니다.

그럼 미로를 조금 뒤틀어볼까요?

 

 

 

DFS는 왼쪽 혹은 오른쪽 벽을 짚고 탐색하는 방법이니까, 왼쪽벽에 손을 짚고 위 미로를 탐색해봅시다.

 

 

 

DFS는 일단 끝까지 탐색하고 봅니다.

그럼, BFS로 풀어볼까요?

 

 

 

위와 같이, 미로의 오른쪽 부분을 굳이 끝까지 탐색할 필요가 없이 출구를 찾을 수 있었습니다.

 

그럼, 이렇게도 생각해볼 수 있습니다.

BFS를 잘 쓰면 최단경로를 구하는데 적합하겠네?

맞습니다.

위 DFS를 사용했던 방법은 오른쪽 미로를 모두 다 탐색하고 왔지만,

BFS의 경우는 출구를 처음 찾았을 때, 그 경로가 최단 경로가 됩니다.

유명한 최단경로 알고리즘인 다익스트라 최단 경로 알고리즘도

BFS를 이용한 최단경로 찾기 아이디어에 기반을 두고 있는 알고리즘입니다.

 

 

그럼, DFS는 BFS에 비해 뭐가 낫지?

DFS는 그래프를 탐색하는데 있어 경향성 혹은 경로의 특징을 지정할 수 있습니다.

 

 

사이클 유무 파악

 

 

해당 그래프의 경우, 사이클이 있습니다.

그래프가 입력되었을 때, 해당 그래프에서 사이클이 생겼는지 DFS를 사용해 사이클의 유무를 판단할 수 있습니다.

 

 

 

DFS를 사용해 탐색하다가, 이미 방문한 노드를 또 방문하게 되었을 때,

이는 사이클이 있다고 볼 수 있죠.

 

 

 

해가 깊은 곳에 있을 경우 + 가지치기 (백트래킹)

 

 

위와 같은 그래프가 있다고 했을 때,

BFS로 탐색을 할 경우 어떻게 될까요?

 

 

 

BFS는 한 깊이씩 탐색을 하므로,

그래프가 거대할 수록, 해가 깊은 곳에 위치할 수록 찾고자 하는 해의 탐색이 느리다는 특징이 있습니다.

 

 

 

 

하지만 DFS를 통해 탐색의 경향성, 특징을 지정해 놓는다면?

가능한 깊게 탐색하면서 해당 경로가 더 이상 유망하지 않다고 판단할 경우,

빠르게 포기하여 부모 노드로 가 다른 경로를 탐색할 수 있습니다.

이를 가지 치기라고도 하며, 백트래킹(Back Tracking, 후퇴 탐색)의 기본 원리 중 하나입니다.

 

물론 특정 해를 찾는 것이 아니라 그래프의 모든 정점을 탐색하는 것이라면 DFS와 BFS 어떤 것을 사용해도 무방합니다.

 

 

 

DFS와 BFS 직접 코드로 구현 해보기

 

 

위와 같은 그래프가 있을 때,

해당 그래프를 DFS와 BFS로 탐색해봅시다.

 

 

DFS 1 - 스택

DFS를 구현하는 방법에는 스택과 재귀가 있습니다.

어느 것을 구현해도 무방하며, 스택을 사용해 한 번 구현해보겠습니다.

스택을 잘 모르겠다면 아래 글을 보고 와주세요.

https://uknowblog.tistory.com/360

[자료구조] 스택, 큐, 데크 - 자료구조 삼대장

 

 

 

 

먼저, 그래프의 연결관계를 인접행렬로 표현하였습니다.

arr[2][8] = 2은 8번 노드와 4번 노드가 연결되어 있음을 의미하며, 0은 연결되지 않음을 의미합니다.

그래프가 가중치를 갖고 있지 않다면 boolean(true/false)로 표현하여도 됩니다.

 

 

 

중복방문을 방지할 visited 배열 하나를 선언합니다.

2번 노드와 8번 노드가 연결되어 있으면,

2번 노드를 탐색하고 연결된 8번 노드를 탐색할 때,

8번 노드와 연결된 2번 노드를 탐색하여

무한한 루프에 빠질 수 있기 때문입니다.

 

 

 

 

스택에 시작 노드인 0번 노드를 넣고, 방문체크(visited[0] = true) 한 뒤,

스택이 빌 때 까지 while문을 반복합니다.

스택에서 하나씩 꺼내며,

해당 노드와 연결되어 있는 다른 노드들(connection[a][b] = 1 인 경우)을 탐색합니다.

물론 방문하지 않은(visited[i] == false) 노드들 중에서요.

 

연결된 노드 중, 방문되지 않은 노드를 찾았다면

방문체크를 한 뒤, 해당 노드를 다시 스택에 넣습니다.

이 과정을 스택이 모두 빌 때까지 반복합니다.

 

스택에서 노드를 하나 꺼낼 때 마다,

해당 노드와 연결된 다른 노드들을 스택에 추가하고,

스택에서 또 다른 노드를 꺼내고, 또 다시 연결된 노드를 스택에 넣고...

이 과정이 모든 노드를 탐색하거나 특정 해를 찾을 때 까지 반복되는 것 입니다.

 

 

이 과정을 스택이 모두 빌 때까지 반복합니다.

 

해당 그래프의 탐색 과정을 나타내봤습니다.

0 -> 5 -> 8 -> 6 과 같이, 최대한 깊게 들어간 후

경로를 모두 다 탐색했다면 뒤돌아오는 방식입니다.

 

 

 

DFS 2 - 재귀

DFS를 구현하는 두 번째 방법은 재귀입니다.

역시나 인접배열과 인접리스트 중 무엇을 사용해도 무방하나,

위에서 인접배열을 사용했으므로 인접리스트를 사용해 구현해봤습니다.

 

 

 

인접 리스트는 ArrayList 배열(혹은 ArrayList<ArrayList<Integer>>)를 사용하여 구현할 수 있습니다.

5번 노드와 0, 4, 8, 7 노드가 연결되어 있다면

connect[5].add(0), connect[5].add(4), connect[5].add(7),  connect[5].add(8) 과 같이

한 노드에 연결된 다른 노드들을 추가하는 방식이죠.

 

 

 

dfs는 재귀로 구현한 모습입니다.

마찬가지로 한 노드와 연결된 다른 노드를 매개변수로 넘겨주어

재귀적으로 호출하는 방식이죠.

 

재귀적으로 호출한 함수가 종료되면, 해당 함수를 호출한 이전 함수로 돌아가기 때문에

재귀의 작동 방식은 스택과 꽤나 비슷합니다. (깊게 따지면 좀 다릅니다)

 

 

 

 

방문 순서는 조금 다를 수 있습니다.

stack 특성 상 연결된 모든 노드를 넣은 뒤, 맨 뒤에 있는 노드를 하나씩 꺼내서

연결된 노드가 여러개라면 번호가 높은 순으로 탐색합니다.

 

반면 재귀로 구현할 경우 연결된 모든 노드를 한 번에 넣고 맨 뒤에서 꺼내는 방식이 아닌,

연결된 노드를 만날 때 마다 재귀적으로 호출하는 방식이기 때문에

연결된 노드가 여러개라면 번호가 낮은 순으로 탐색합니다.

 

특정 조건(ex> 연결된 노드가 여러개라면 낮은순으로)이 있는 게 아니라면 별 문제는 되지 않으며,

코드를 조금 수정해서 낮은 순/높은 순으로 탐색하는 건 그리 어렵지는 않습니다.

 

사실 중요한 것은 방문 순서보다는 재귀든 스택이든, 깊이를 우선적으로 탐색한다는 점이기도 하고요.

DFS를 구현할 때 재귀와 스택 둘 중 어떤 방법을 사용해도 무방하나,

재귀로 구현하는게 보다 깔끔하기 때문에 대부분은 재귀적으로 구현합니다.

 

 

 

BFS

DFS가 스택(Stack) 혹은 재귀를 사용하였다면,

BFS는 큐(Queue)를 사용해 구현합니다.

 

 

먼저 큐를 하나 만들고, 시작노드인 0을 삽입합니다.

0번 노드를 방문처리 하면 bfs를 시작할 준비는 끝났습니다.

 

 

 

구조 자체는 스택을 사용한 DFS와 크게 다르지 않습니다.

한 노드를 큐에서 꺼낸 뒤,

해당 노드와 연결된 노드 중에서 방문하지 않은 노드를 찾아

큐에 넣고 방문처리를 해줍니다.

위 과정을 큐가 빌 때 까지 반복합니다.

 

 

 

DFS와는 사뭇 다른 결과가 나왔습니다.

 

BFS는 시작 노드로부터 거리가 1인 노드, 거리가 2인 노드, 거리가 3인 노드 ... 거리가 n인 노드로 탐색합니다.

 

0번 노드로부터 거리 1

0번 노드에서 시작하여, 0번 노드로부터 깊이 1만큼 떨어져있는 1, 4, 5번 노드를 탐색했습니다.

 

0번 노드로부터 거리 2

1, 4번 노드에서 연결된 다른 노드는 없으므로 탐색을 종료하고,

5번 노드에서 연결된 7, 8번 노드를 탐색합니다.

 

0번 노드로부터 거리 3

이후 7번 노드와 연결된 3번 노드를, 8번 노드와 연결된 2, 6번 노드를 탐색합니다.

모든 노드를 탐색했으므로 BFS 탐색을 종료합니다.

 

 

후기

생각보다 글이 길어졌네요.

최대한 설명하긴 했는데,

역시 배우는 것 보다 남에게 설명하는 것이 더 어려운 것 같습니다.