11. 너비 우선 탐색(Breath First Search) 알고리즘 [디딤돌 자료구조와 알고리즘 with C++]

언어 자료구조 알고리즘/[C++]디딤돌 자료구조와 알고리즘

11. 너비 우선 탐색(Breath First Search) 알고리즘 [디딤돌 자료구조와 알고리즘 with C++]

언제나휴일 2016. 4. 12. 14:41

11. 너비 우선 탐색(Breath First Search)

이번에는 그래프에서 최단 경로를 찾는 너비 우선 탬색(Breath First Search) 알고리즘을 알아보아요.

앞에서 다룬 깊이 우선 탐색(Depth First Search)알고리즘은 그래프 상에서 두 정점 사이에 경로를 찾는 알고리즘이었습니다. 한 정점에서 갈 수 있는 다음 정점으로 이동하고 다시 다음 정점으로 이동하면서 경로를 찾는 것을 반복하였습니다. 만약 더 이상 이동할 곳이 없다면 이전에 이동했었던 곳에서 다시 찾는 형태로 경로를 찾는 알고리즘입니다.

너비 우선 탐색 (Breath First Search)

위 그래프에서 0에서 8로 가는 정점을 예로 들어 볼게요. 여기에서는 한 정점에서 다음 정점으로 갈 때 높은 수를 갖는 정점을 우선 방문하는 예로 설명할게요.

깊이 우선 탐색 알고리즘에서는 출발지 0을 먼저 방문합니다. 그리고 0에서 이웃하는 두 개의 정점 중에 하나를 방문(0, 2)합니다. 그리고 마지막 방문한 정점 2에서 이웃하는 정점(0, 1, 4) 중에 가 본 적이 없는 정점을 하나 방문(0, 2, 4)합니다. 그리고 마지막 방문한 정점 4에서 이웃하는 정점(2, 5, 6, 7) 중에 가 본 적이 없는 정점을 하나 방문(0, 2, 4, 7)합니다. 다시 마지막에 방문한 7에서 이웃하는 정점(4) 중에 가 본 적이 없는 정점을 방문해야 하는데 그런 정점이 없습니다.

이처럼 더 이상 방문할 곳이 없으면 이전에 방문(0, 2, 4)의 마지막 방문한 정점 4에서 이웃하는 정점(2, 5, 6, 7)에서 가 본 적이 없는 정점을 하나 방문(0, 2, 4, 6)합니다. 다시 6과 이웃하는 정점(3, 4, 8) 중에 가 본 적이 없는 정점을 하나 방문(0, 2, 4, 6, 8)합니다. 마지막 방문한 곳이 목적지이므로 0과 8 사이에 경로를 찾았습니다. 이를 계속 반복하면 두 정점 사이에 갈 수 있는 모든 경로를 찾을 수 있습니다.

실제 구현할 때 인접 행렬로 구현하면 재귀적인 코드로 간단하게 구현할 수도 있습니다. 하지만 정점의 개수가 많아지면 재귀의 깊이가 깊어져서 스택을 사용하는 것이 나을 수 있습니다. 또한 인접 행렬보다 정점과 간선의 집합으로 표현하면 그래프에 정점이나 간선 추가 등이 쉽고 필요없는 간선 정보를 갖지 않을 수 있어서 성능에 유리합니다. 물론 정점이 많을 때 얘기입니다.

이 책에서는 앞에서 인접 행렬과 스택을 이용한 깊이 우선 탐색 알고리즘과 정점과 간선의 집합으로 그래프를 표현한 후에 스택을 이용한 깊이 우선 탐색 알고리즘을 소개하고 구체적인 코드를 설명하고 있습니다. 인접 행렬과 재귀적인 방법을 사용하는 방법과 코드는 쉽게 웹 검색을 통해 확인할 수 있으니 여기에서는 설명을 생략할게요.

Foots: 0

Foots: 0 2

Foots: 0 2 4

Foots: 0 2 4 7

Foots: 0 2 4 6

솔루션 Foots: 0 2 4 6 8

Foots: 0 2 4 6 3

Foots: 0 2 4 6 3 1

Foots: 0 2 4 5

Foots: 0 2 1

Foots: 0 2 1 3

Foots: 0 2 1 3 6

솔루션 Foots: 0 2 1 3 6 8

Foots: 0 2 1 3 6 4

Foots: 0 2 1 3 6 4 7

Foots: 0 2 1 3 6 4 5

Foots: 0 1

Foots: 0 1 3

Foots: 0 1 3 6

솔루션 Foots: 0 1 3 6 8

Foots: 0 1 3 6 4

Foots: 0 1 3 6 4 7

Foots: 0 1 3 6 4 5

Foots: 0 1 3 6 4 2

Foots: 0 1 2

Foots: 0 1 2 4

Foots: 0 1 2 4 7

Foots: 0 1 2 4 6

솔루션 Foots: 0 1 2 4 6 8

Foots: 0 1 2 4 6 3

Foots: 0 1 2 4 5

너비 우선 탐색은(Breath First Search)은 출발 정점에서 가까운 거리의 경로를 우선적으로 방문하면서 최단 거리를 찾는 알고리즘입니다.

위 그래프에서 0에서 8까지 가는 경로 중에 최단 경로를 BFS 알고리즘으로 찾아봅시다. 먼저 위 그래프에서 출발지 0을 먼저 방문합니다. 현재 경로의 합은 0입니다.

이제 출발지에서 경로의 합이 1인 정점들을 방문합니다. 현재까지의 경로는 (0, 1)과 (0, 2)입니다.

출발지에서 경로의 합이 2인 정점들을 방문합니다. 현재까지의 경로는 (0, 1, 2), (0, 1, 3), (0, 2, 1), (0, 2, 4)예요.

경로의 합이 3인 정점들을 방문합니다. (0, 1, 2, 4), (0, 1, 3, 6), (0, 2, 1, 3), (0, 2, 4, 5), (0, 2, 4, 6), (0, 2, 4, 7)이죠.

경로의 합이 4인 정점들을 방문합니다. (0, 1, 2, 4, 5), (0, 1, 2, 4, 7), (0, 1, 2, 4, 7), (0, 1, 3, 6, 4), (0, 1, 3, 6, 8), (0, 2, 1, 3, 6), (0, 2, 4, 6, 3), (0, 2, 4, 6, 8), (0, 1, 2, 4, 6, 3), (0, 1, 2, 4, 6, 8), (0, 1, 3, 6, 4, 2), (0, 1, 3, 6, 4, 5), (0, 1, 3, 6, 4, 7), (0, 2, 1, 3, 6, 4), (0, 2, 1, 3, 6, 8)

목적지에 가장 먼저 도착한 것 중에 처음으로 발견한 경로는 (0, 1, 3, 6, 8)입니다. 다음은 큐가 빌 때까지 테스트하였을 때 결과입니다.

찾는중 Foots: 0

찾는중 Foots: 0 1

찾는중 Foots: 0 2

찾는중 Foots: 0 1 2

찾는중 Foots: 0 1 3

찾는중 Foots: 0 2 1

찾는중 Foots: 0 2 4

찾는중 Foots: 0 1 2 4

찾는중 Foots: 0 1 3 6

찾는중 Foots: 0 2 1 3

찾는중 Foots: 0 2 4 5

찾는중 Foots: 0 2 4 6

찾는중 Foots: 0 2 4 7

찾는중 Foots: 0 1 2 4 5

찾는중 Foots: 0 1 2 4 6

찾는중 Foots: 0 1 2 4 7

찾는중 Foots: 0 1 3 6 4

===== 솔루션===== Foots: 0 1 3 6 8

찾는중 Foots: 0 2 1 3 6

찾는중 Foots: 0 2 4 6 3

===== 솔루션===== Foots: 0 2 4 6 8

찾는중 Foots: 0 1 2 4 6 3

===== 솔루션===== Foots: 0 1 2 4 6 8

찾는중 Foots: 0 1 3 6 4 2

찾는중 Foots: 0 1 3 6 4 5

찾는중 Foots: 0 1 3 6 4 7

찾는중 Foots: 0 2 1 3 6 4

===== 솔루션===== Foots: 0 2 1 3 6 8

찾는중 Foots: 0 2 4 6 3 1

찾는중 Foots: 0 2 1 3 6 4 5

찾는중 Foots: 0 2 1 3 6 4 7

그런데 실제 프로그래밍에서 현재까지 경험한 경로를 큐에 보관해 두었다가 꺼내와서 다음 경험한 경로를 조사한 후에 목적지에 도달했는지 확인하여 도달하지 않았을 때 큐에 보관하는 형태로 한다면 결과는 보다 빠르게 확인할 수 있습니다. 다음은 큐를 이용하여 다음 경험한 경로를 조사한 후에 목적지에 도달하였는지 확인하는 과정으로 프로그래밍했을 때 결과입니다.