BFS와 DFS의 기초 개념 -1

오늘은 BFS와 DFS의 기초 개념부터 차근차근 설명하려고 합니다.

(해당 포스트는 BFS와 DFS의 개념을 모르는 초보분들을 초점으로한 포스팅입니다.) 

우선, 그래프는 정점과 간선으로 이루어진 자료구조라고 할 수 있습니다.

아래 그림을 살펴보겠습니다.

이 그림에서 동그라미로 표시된 1부터 6까지는 정점(Vertex) 라고 불리며, 각 노드를 연결하는 직선을 간선(Edge)이라고 합니다. (포스팅에서는 정점을 노드라고 칭하겠습니다.....제가 좀 익숙해서)

너비우선탐색(BFS)와 깊이우선탐색(DFS)는 어느 한 노드로부터 시작해서 원하는 노드로까지 탐색하는 방법을

가르키는 알고리즘이라고 할 수 있습니다.

1. 너비우선탐색(BFS)

너비우선탐색은 말그대로 현재 노드와 인접한 노드들부터 탐색하는 방법입니다.

예를 들어, 1번 노드부터 시작해서 모든 노드를 방문하기 위해 걸리는 시간을 구한다고 가정해봅시다.

(각 노드간의 이동시간은 1초가 걸린다고 하겠습니다.)

[1초 경과]

1번 노드부터 시작해서 1초가 경과하게 되면 1번 노드와 인접한 2번, 6번 노드를 방문하게 됩니다.

[2초 경과]

2초 후에는, 2번 노드와 6번 노드와 인접한 노드를 방문할 차례이지만, 2번, 6번 노드와 인접한 1번 노드는

이미 방문했으므로 또 다시 방문할 필요가 없어집니다. 그렇기 때문에 2번 노드와 연결된 3번, 4번 노드를

방문하게 됩니다.

[3초 경과]

마찬가지로 3초 후에는 3번, 4번 노드와 인접한 노드를 방문할 차례이지만, 2번 노드는 이미 방문한 상태이므로 또 다시 방문할 필요가 없어집니다. 그렇기 때문에 3번, 4번 노드와 인접한 5번 노드를 방문하게 됩니다.

결과적으로, 1번 노드부터 5번 노드까지 걸리는 시간은 총 3초입니다. BFS의 탐색 방향을 보시면 시작 노드와

인접한 노드들을 모두 방문한다는 것이 핵심입니다.

BFS의 탐색 노드의 순서를 살펴보면 아래 그림과 같습니다.

여기서, 주의할 점은 3번 노드와 4번 노드를 통해 동시에 5번 노드에 접근하는 것 처럼 보이지만, 사실 3번 노드가 먼저 5번 노드에 접근했다면 4번 노드를 통해서 5번 접근할 필요가 없어집니다.

어떤 노드(3번일지 4번일지)를 통해 5번 노드를 접근할 지는 사실 2번 노드에 저장된 순서에 따라 바뀌게 됩니다. (이는 아래 코드 레벨에서 확인하겠습니다.)

2. 깊이우선탐색(DFS)

해당 노드와 인접한 모든 노드들부터 탐색하는 너비우선탐색과는 달리, 깊이우선탐색은 해당 노드와 인접한 노드중 하나의 노드를 선택해 연달아 탐색해 나가는 과정입니다.

마찬가지로, 1번 노드부터 시작해서 모든 노드를 방문하기 위해 걸리는 시간을 구한다고 가정해봅시다.

(각 노드간의 이동시간은 1초가 걸린다고 하겠습니다.)

[1초 경과]

1번 노드부터 시작해서 1초가 경과하게 되면 1번 노드와 연결된 2번, 6번 노드중 하나의 노드를 선택합니다.

그림에서는 2번 노드를 선택해서 방문하였습니다.

[2초 경과]

2초 후에는, 2번 노드와 연결되어 있는 1번, 3번, 4번, 6번 노드중 하나의 노드를 선택합니다.

하지만 1번 노드는 이미 방문한 상태이므로 방문할 필요가 없습니다.

그림에서는 그 다음으로 3번 노드를 방문합니다.

[3초 경과]

2초 후에는, 3번 노드와 연결되어 있는 2번 노드와 5번 노드중 하나의 노드를 선택합니다.

하지만 2번 노드는 이미 방문한 상태이므로, 5번 노드를 방문합니다.

[4초 경과]

4초 후에는, 5번 노드와 연결되어 있는 3번 노드와 4번 노드중 하나의 노드를 선택합니다.

하지만 3번 노드는 이미 방문한 상태이므로, 4번 노드를 방문합니다.

[5초 경과]

5초 후에는, 4번 노드와 연결되어 있는 2번 노드와 5번 노드중 하나의 노드를 선택합니다.

하지만 2번 노드와 5번 노드 모두 이미 방문한 상태이므로, 아직 방문하지 않은 6번 노드를 방문해야 합니다.

주의 사항)

(이때, 방문하지 않은 6번 노드를 방문하기 위해서 현재 탐색중인 4번노드를 통해서 곧바로 6번 노드를 탐색하는 것이 아닙니다. 

4번 노드는 더 이상 탐색할 노드가 없기 때문에 탐색을 종료하고 1번 노드 입장에서 아직 탐색하지 않은 노드가 있다면(6번 노드) 해당 노드부터 다시 탐색을 시작하는 것입니다.)

DFS의 방문 순서를 살펴보면 다음과 같습니다.

BFS와 다른 점은, 탐색 방향이 한 방향으로 이루어지는 것을 볼 수 있습니다. 

1번 노드와 인접한 노드들 중 하나인 2번 노드로 뻗어나가면서 탐색을 진행하고 2번 노드에서 탐색할 수 있는 모든 노드들을 탐색했다면, 다시 1번 노드로 돌아와 방문하지 않은 노드(6번 노드)를 탐색하는 것입니다.

※ 이번 시간은 BFS와 DFS의 개념에 대해서 간략히 살펴보았습니다.

다음 시간에는 BFS와 DFS를 구현하기 전, 노드간의 연결 정보를 저장할 수 있는 법에 대해서

코드 레벨 수준에서 살펴보도록 하겠습니다.

2019/02/11 - [늦깍이 IT] - BFS와 DFS의 기초 개념 -2