Graph(DFS 깊이 우선 탐색)

코딩테스트를 위해 백준이나 프로그래머스를 보다보면 DFS, BFS 용어에 대해서 한 번쯤은 듣게 될 것이다. DFS 원리와 BFS 원리를 적용하면 최단 경로를 쉽게 찾을 수 있다고 하는데, 오늘은 그 원리에 대해 알아보자.

 

DFS(깊이 우선 탐색)

• 하나의 정점을 방문한다.
• 이웃한 정점으로 갈 수 있다면 무조건 이웃 정점 하나로 방문한다.(과거에 방문하지 않은 새로운 정점)
• 시작점으로부터 점점 깊어지는 노드로 전진하게 된다.
• 방문 가능한 이웃 정점이 없다면 backtracking을 통해 경로 상 가장 최근 방문했던 정점으로 돌아가서 또다른 새로운 노드 방문을 시도 한다.(stack 이용)
• 반드시 오름차순에 따라 이동한다.(경로상 갈림길을 만났을 때)
• 새로운 이웃한 노드가 존재하면 stack에 위치한 지점을 push하고 이웃 노드로 이동
• 방문 가능한 노드가 없으면 해당 노드를 push 하지 않고 pop하면서 backtracking 위치로 이동

 

이러한 그래프 G7을 가지고 DFS 원리를 적용하여 최단 경로를 찾아보자.

   stack

stack 하나를 준비하고 push와 pop을 통해 인접 노드를 방문할 것이다.

 

1) A가 시작정점이라면 오름차순 원리에 따라 B로 이동한다.(stack에 시작 정점 A push)

A

   stack

 

2) B에서 오름차순 원리에 따라 D로 이동한다.(stack에 B를 push하면서 D로 이동)

B

A

   stack

 

3) D에서 이웃 정점 G로 이동한다.(stack에 D를 push하면서 G로 이동)

D

B

A

   stack

 

4) G의 이웃정점 중 오름차순에 의해 E로 이동한다.(stack에 G를 push하면서 E로 이동)

G

D

B

A

   stack

 

5) E의 이웃정점 C로 이동한다.(stack에 E를 push하면서 C로 이동)

E

G

D

B

A

   stack

 

6) C가 더이상 갈 곳이 없기 때문에 push 하지 않고 backtracking을 위해 pop하면서 다시 E로 되돌아 온다.

(stack에서 pop -> E가 pop됨)

G

D

B

A

   stack

 

7) E에 인접한 모든 정점이 과거에 방문했던 정점이므로 backtracking을 위해 pop하면서 G로 되돌아 온다.

(stack에서 pop -> G가 pop됨)

D

B

A

   stack

 

8) G에서 이웃한 정점 F로 이동한다.(stack에 G가 다시 push)

G

D

B

A

   stack

 

9) 모든 정점을 거쳐서 마지막 정점에 도착했으므로 stack에서 모두 pop한다.

stack에서 pop시킨 순서들을 다른 배열에 담아 나열해 보면 E G G D B A 순서이다.

 

<코딩 구현>

 

위와 같이 DFS 알고리즘을 C언어 코딩으로도 구현할 수 있었다.