[알고리즘] 깊이 우선 탐색(Depth-First Search, DFS)

그래프에서 모든 정점을 방문하는 방법 중 하나인 깊이 우선 탐색(Depth-First Search, DFS)에 대해 공부하고자 한다. 그래프의 모든 정점을 방문하는 DFS와 BFS는 간단하지만 그래프의 알고리즘에서 핵심적인 위치를 차지한다. 따라서 반드시 알아야 할 알고리즘들 중 하나이며, 코딩테스트에도 빈번히 출제되는 유형이다. 이와 더불어 너비 우선 탐색(Breadth-First Search, BFS)도 있다. 이는 다음에 공부해보도록 한다.

 

DFS는 BFS에 비해 구현이 간단하나, 검색 자체 속도는 BFS보다 느린 편이다.

 

DFS는 루트(Root)의 자식 정점을 하나 방문한 다음 아래로 내려갈 수 있는 곳 까지 내려간다. 더 이상 내려갈 수 없으면 위로 되돌아오다가 내려갈 곳이 있으면 즉각 내려간다.

 

출처: https://velog.io/@sukong

---

다음과 같이 정점이 8개인 무향 그래프에서의 DFS를 수행하는 예를 보자. (+ DFS를 구현할 때 사용될 visit[] 배열과 함께 보면 더 좋다.)

 

1) 예를 들어 정점 1을 시작 정점으로 정했다면, 1을 방문하면서 Start

visit[1] = true

visit[2] = false

visit[3] = false

visit[4] = false

visit[5] = false

visit[6] = false

visit[7] = false

visit[8] = false

 

 

2) 정점 1에서 방문할 수 있는 정점 중 한 개를 방문한다. (1 -> 2)

visit[1] = true

visit[2] = true

visit[3] = false

visit[4] = false

visit[5] = false

visit[6] = false

visit[7] = false

visit[8] = false

 

3) 정점 2에 인접하며 방문하지 않은 정점은 총 3개이다. 이 중 하나를 방문한다. (2 -> 3)

visit[1] = true

visit[2] = true

visit[3] = true

visit[4] = false

visit[5] = false

visit[6] = false

visit[7] = false

visit[8] = false

 

4) 정점 3에서 인접하고 방문하지 않은 정점은 1개 이므로 그 정점을 방문한다. (3 -> 4)

visit[1] = true

visit[2] = true

visit[3] = true

visit[4] = true

visit[5] = false

visit[6] = false

visit[7] = false

visit[8] = false

 

5) 정점 4에 인접하고 방문하지 않은 정점은 1개 이므로 그 정점을 방문한다.(4 -> 5)

visit[1] = true

visit[2] = true

visit[3] = true

visit[4] = true

visit[5] = true

visit[6] = false

visit[7] = false

visit[8] = false

 

6) 정점 5에 인접한 정점 중 방문하지 않은 정점은 없으므로 왔던 길로 되돌아간다. (5 - 4 - 3 - 2) 정점 2에 인접하고 방문하지 않은 정점이 있으므로 그 정점을 방문한다. (2 -> 6)

visit[1] = true

visit[2] = true

visit[3] = true

visit[4] = true

visit[5] = true

visit[6] = true

visit[7] = false

visit[8] = false

 

7) 정점 6에 인접하고 방문하지 않은 정점은 2개 이므로 두 정점 중 하나를 방문한다. (6 -> 7)

visit[1] = true

visit[2] = true

visit[3] = true

visit[4] = true

visit[5] = true

visit[6] = true

visit[7] = true

visit[8] = false

 

8) 정점 7과 인접하고 방문하지 않은 정점은 없으므로 왔던 길로 되돌아간다. (7 - 6) 정점 6과 인접하고 방문하지 않은 정점이 1개 있으므로 그 정점을 방문한다. (6 -> 8)

visit[1] = true

visit[2] = true

visit[3] = true

visit[4] = true

visit[5] = true

visit[6] = true

visit[7] = true

visit[8] = true

 

final) 정점 8과 인접한 정점 중 방문하지 않은 정점은 없으므로 왔던 길을 되돌아간다. (8 - 6 - 2 - 1) 정점 1과 인접한 정점 중 방문하지 않은 정점은 없다. 모든 정점을 방문하였으므로 DFS는 종료된다.

 정점의 방문 순서는 (1 - 2 - 3 - 4 - 5 - 6 - 7 - 8)이다.

---

이제 프로그래밍 적으로 구현을 해보자. 위와 같은 그래프는

1) 인접 행렬

2) 인접 리스트

로 구현할 수 있다.

 

인접 행렬은 다음과 같이 쓸 수 있다.

	0	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0	0
1	0	0	1	0	0	0	1	0	1
2	0	1	0	1	0	0	1	0	0
3	0	0	1	0	1	0	0	0	0
4	0	0	0	1	0	1	0	0	0
5	0	0	0	0	1	0	0	0	0
6	0	1	1	0	0	0	0	1	1
7	0	0	0	0	0	0	1	0	0
8	0	1	0	0	0	0	1	0	0

무향 그래프에서 인접 행렬은 대각선을 기준으로 대칭이다.

 

인접 그래프는 다음과 같이 쓸 수 있다.

1	2 - 6 - 8
2	1 - 3 - 6
3	2 - 4
4	3 - 5
5	4
6	1 - 2 - 7 - 8
7	6
8	1 - 6

인접 그래프를 가지고 그래프의 정점 방문 순서를 살펴볼까 한다.

만일 정점 1을 시작 정점으로 한다면...

 

1 방문 -> (2 6 8 중 2) ->

2 방문 -> (1 3 6 중 1은 visit이므로 3) ->

3 방문 -> (2 4 중 2는 visit이므로 4) ->

4 방문 -> (3 5 중 3은 visit이므로 5) ->

5 방문 -> (4는 visit 이므로 return) -> 4 -> 3 ->

2로 귀환 -> (1 3 6 중 1 3은 visit이므로 6) ->

6 방문 -> (1 2 7 8 중 1,2는 visit이므로 7) ->

7 방문 -> (6은 visit이므로 return) -> 

6으로 귀환 -> (1 2 7 8중 1,2,7은 visit이므로 8) ->

8 방문 -> (1 6 중 1,6은 visit이므로 return) -> 6 -> 2 -> 1 -> 종료

 

* DFS의 알고리즘

DFS(v) {
	
    visit[v] -> True
    
    for x in L(v) // L(v) : 정점 v의 인접 정점 집합
    	if(visit[x] = False then
        	DFS(x)
}            

 정점 v에 대해 DFS(v)가 호출되면 먼저 정점 v를 방문하였다(visit[v] = true)로 표기한다. 이와 인접한 정점 중 방문하지 않은 정점에 대해 각각 DFS를 호출한다. 정점 v에 인접한 정점 중 방문하지 않은 정점y, z이 있더라도 x에 대해 DFS를 호출하면 DFS는 일단 깊이 들어갈 수 있는 데까지 들어가기 때문에 정점 y나 정점 z가 다른 정점과 인접하면 방문될 수도 있다. 즉 DFS(v)에서 x에 대해 DFS를 끝내고 돌아오면 방문하지 않은 상태였던 정점 y나 정점 z가 방문된 상태가 되어 이들에 대해 DFS를 수행할 필요가 없게 되는 상황은 매우 흔하다. 궁극적으로 모든 정점에 대해 DFS()가 한번 씩 호출된다. DFS의 수행 시간은 θ(V + E)이다. (V : 정점의 개수, E : 간선의 개수)

 

 여기서 DFS는 모두 연결 그래프를 가정한 것이다. 만일 분리된 두 개 이상의 부분 그래프가  있다면 DFS를 부분 그래프의 수만큼 수행해야 모든 정점을 방문할 수 있다.

 

# DFS 구현

static boolean[] visit;
static int[][] graph;

static void DFS(int start){

        visit[start] = true; //정점 방문 완료
        System.out.printf("%d ", start);

        for(int a : graph[start])
            if(graph[start][a] != 0 && !visit[graph[start][a]])
                DFS(graph[start][a]);
    }