DFS(깊이 우선 탐색) 알고리즘

오늘 공부할 알고리즘은 깊이 우선 탐색, 흔히 DFS(Depth-First Search)로 알려져 있는 알고리즘이다. 이 알고리즘은 모든 노드를 방문하고자 하는 경우에 사용하게 된다. 

(cf. 맹목적 탐색(blind search)란, 이미 정해진 순서에 따라 상태 공간 그래프를 점차 형성해 가면서 해를 탐색하는 방법)

짧게 설명하자면 루트 노드(혹은 다른 임의의 노드)에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.

1. 깊이 우선 탐색의 특징

1. 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.

2. 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.

3. 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이다.

-> 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.

* 만약, 구현하려고 하는 알고리즘이 트리가 아닌 그래프를 탐색하게 된다면 약간의 변화가 필요하다. 우선적으로는 그래프의 깊이(depth)를 결정할 필요가 있다. 루트 노드(가상 최상위에 위치한 노드)의 깊이는 0으로 하며, 임의의 노드의 깊이는 이의 '부모 중 가장 깊이가 작은 것'의 깊이에 '1'을 더한 값으로 정의한다. 

2. 깊이 제한과 백트래킹

탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)를 사용한다. 깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면 최근에 첨가된 노드의 부모노드로 돌아와서, 부모노드에서 이전과는 다른 동작자를 적용하여 새로운 자식노드를 생성한다. 여기서 부모노드로 되돌아 오는 과정을 백트래킹(backtracking)이라고 한다.

3. 장점과 단점

1. 장점

- 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.

- 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

2. 단점

- 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 깊이제한을 통하여 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.

- 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이 때 얻어진 해는 최적의 해가 아닐 수 있다는 의미이다.

4. 알고리즘(논리)

0. 방문하게 될 노드를 스택에 push한다.

1. 시작 노드(A)를 방문한다.

2. 방문한 노드(A)는 방문했다고 표시한다.  (방문 표시: 스택에 넣은 적이 있느냐)

3. 방문한 노드(A)와 인접한 노드(B, C ...)들을 차례로 순회한다.

4. 방문한 노드(A)와 이웃한 노드(B)를 방문했다면, A와 인접한 또 다른 노드를 방문하기 전에 B의 이웃 노드들을 전부 방문해야 한다.

4-1.  B를 시작 정점으로 1번으로 다시 올라간다.

5. B의 분기를 전부 완벽하게 탐색했다면, 다시 A에 인접한 정점들 중 아직 방문이 안 된 정점을 찾는다.

6. 아직 방문이 안 된 정점이 없으면 종료한다.

5. 논리구조 코드

1. 방문하게 될 노드를 스택에 push

2. while문 진입 - 조건: 스택이 비어있지 않을 동안

2-1. 스택에서 하나의 노드를 꺼냄

2-2. 꺼낸 노드와 연결되었으면서 방문하지 않은 노드가 있다면

3-1. 스택에 push

3-2. 해당 노드 flag 배열 true

3-3. while문안의 flag 변수 true

3-4. break // break문으로 깊이 우선 탐색이 가능

2-3. while문 변수 flag가 false 라면 새로운 스택 pop()

구현 방법에는 순환 호출과 명시적 스택 2가지가 있다.