박두현의 컴퓨터 이론들 - 너비우선탐색 & 깊이우선탐색 알고리즘

안녕하세요. 박두현 입니다.

오늘은 탐색 알고리즘을 알아볼까 합니다. 아주 즐거운 시간이 되겠죠?

1. 너비우선탐색 알고리즘(Breadth First Search Alg.)은 무엇인가?

너비우선탐색 알고리즘은 아래와 같이 돌아갑니다.

1. 시작노드를 큐(Queue)에 배정한다.

2. 큐(Queue)가 비어있다면 실패하게 되어 멈춘다.

3. 만일 큐(Queue)의 첫번째 요소가 목표 노드 'g'이면 성공하게 되어 멈춘다. 그렇지 않으면...

4. 큐(Queue)로 부터 첫번째 요소를 제거하고 확장시키며 모든 자식들을 어떤 순서이든지 큐(Queue)의 마지막에 배정한다.

5. 단계2로 돌아간다.

BFS 방법은 다음 레벨의 노드를 조사하기 앞서 트리의 같은 레벨이 있는 레벨의 노드를 먼저 조사하는 방법 입니다.

이것은 자식의 자식들이 고려되기 전에 현 노드의 바로 밑에 있는 자식 노드가 조사된다는 것을 의미 합니다.

BFS 알고리즘은 매우 단순 합니다.

그것은 조사되지 않은 노드들을 제외한 모든 생성된 노드를 저장하기 위해 노드구조를 사용 합니다.

노드의 제거나 조사를 하기위해 노드들이 위치해 있는 순서는 탐색의 형태를 결정 합니다.

BFS의 시간 복잡도는O(b^d) 입니다.

이것은 목표 깊이 d 까지의 모든 노드가 생성됨을 주목하면 알 수 있습니다.

그러므로 생성되는 노드 수는 b + b² + ... + b^d, 즉 O(b^d) 임을 알 수 입니다. 공간 복잡도 역시O(b^d) 입니다.

왜냐하면 주어진 깊이의 모든 노드들은 다음 깊이의 모든 노드들을 생성하기 위해 저장되야만 하기 때문이죠.

즉 깊이 d-1 인 b^d-1 노드들이 깊이 d 의 노드를 생성하기 위해 저장되야만 합니다. 결국 공간 복잡도는 O(b^d) 가 되는거죠.

이러한 지수 함수적인 시간 공간 특성이 BFS 을 잘 적용하지 못하게 하는 이유중의 하나 입니다.

아래 그림을 보세요. 이것이 너비우선탐색 알고리즘의 탐색 방식을 그림으로 표현한 것 입니다.

[너비우선탐색 알고리즘]

2. 깊이우선탐색 알고리즘(Depth First Search Alg.)은 무엇인가?

깊이우선탐색 알고리즘은 아래와 같이 돌아갑니다.

1. 초기 노드 q 를 Queue 에 배정한다.

2. 만일 Queue 가 비어있다면, 실패를 알리고 멈춘다.

3. 만약 Queue 의 첫번째 요소가 목표노드 'q' 이면 성공을 알리고 멈춘다. 그렇지 않으면...

4. 첫번째 요소를 Queue 로부터 제거하고, 그 요소의 자식들이 있다면 그 노드들을 Queue 의 앞(front)에 추가한다.

     (어떤 순서든지)

5. 단계 1로 돌아간다.

DFS은 가능한 빨리 탐색 트리 속으로 들어가서 수행 됩니다.

이것은 최근에 확장된 노드의 자식 노드(chidren node)를 생성함으로써 가능 합니다.

다음에 자식 노드(children node)의 자식 노드를 생성하여 목표가 발견되기까지 혹은 임계 깊이(cutoff depth) d 에 이를 때까지 반복하게 됩니다.

잎 노드(leaf node)에 이를 때 까지 또는 임계점(cutoff point)에서 목표가 발견되지 않으면 프로그램은 최근에 확장된 노드로 역행(back tracking)하여 그 노드의 다른 자식 노드 를 생성 합니다.

이 과정은 목표가 발견되기까지 혹은 실패하게 될 때까지 계속 됩니다.
DFS알고리즘은 Queue 에 위치하는 노드의 순서를 제외하고는 breadth-first search 과 동일하다. DFS은 새로 생성된 자식을 Queue 의 앞에 위치시켜 그것들이 먼저 선택되도록 합니다.

DFS은 탐색 트리가 매우 많은 목표를 갖고 있는 경우에 breadth-first search 보다 더 선호 됩니다.

그렇지 않으면 깊이 우선 탐색은 해답을 발견하지 못할 수도 있습니다.

깊이 임계값(depth cutoff) 역시 몇가지 문제를 야기시킬 수 있습니다. 만약 임계값이 너무 얕으면 목표를 찾지 못할 수 있고, 임계값이 너무 깊으면 추가적인 계산이 필요하게 되죠.
DFS 의 시간 복잡도(time complexity)는 breadth-first search 의 복잡도와 같습니다.

초기 시작 노드로부터 현재 노드로의 path 만 저장되기 때문에 공간은 덜 차지하게 됩니다.

그러므로 만일 깊이 임계값(depth cutoff)이 d 이면, 공간 복잡도는 O(d) 입니다.

아래 그림을 보세요. 이것이 깊이우선탐색 알고리즘의 탐색 방식을 그림으로 표현한 것 입니다.

[깊이우선탐색 알고리즘]

3. BFS vs DFS, 두 알고리즘 비교

# 깊이우선탐색 알고리즘

해가 존재할 가능성 있으면 계속 전진 탐색
스택 구조, 재귀 호출 이용
재귀 호출이 이루어질 때마다 위치가 점점 깊게 들어감
너무 깊게 들어가면 overflow 발생하므로, 막히면 나아갈 곳이 있는 곳으로 돌아가서 과정 반복, 모든 곳을 방문했을 때 탐색 종료

- 유용 : 사이클 탐지(Cycle Detection), 위상 정렬(Topological Sorting)
- 장점 : 무한히 넓은 트리에 효과적
- 단점 : 목표 노드가 없는 경로에 깊이 빠질 수 있음 <- 깊이 제한

# 너비우선탐색 알고리즘

생성된 순서에 따라 노드 확장
큐 구조, 큐의 첫 정점을 보고 그 정점에 인접한 정점들 탐색
새롭게 발견되는 정점 enqueue, 모든 인접 정점 탐색 끝나면 첫 정점 dequeue

- 유용 : 최소신장트리(Minimum Spanning Trees), 최단경로(Shortest Paths)
- 장점 : 무한히 깊거나 무한에 가까운 트리인 경우 효과적

4. 마치면서...

깊이우선탐색과 너비우선탐색은 참 많이 나오는 알고리즘 입니다.

전산공학과 학생들이 알고리즘 시간이면 배우는 재미난 알고리즘 중 하나이기도 합니다. 시험 볼땐 안재미있지만요.

다음엔 어떤 글을 올릴까 너무 고민되네요.

아무튼 다음번에도 재미난 글 올리겠습니다.

날씨가 너무 많이 추운데 다들 감기 조심하시고 건강하세요.