목차

# 그래프 탐색이란

  • 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
  • Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 등등

# 깊이 우선 탐색

깊이 우선 탐색(Depth-First Search)은 DFS라고도 부른다.(이하 DFS라고 하겠다.)

루트 노트(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

  • 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
  • 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
  • 사용하는 경우 : 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.
  • DFS가 BFS보다 좀 더 간단하다.
  • 단순 검색 속도 자체는 BFS에 비해서 느리다.

DFS의 특징

  • 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
  • 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
  • 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이다.
    • 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.

DFS 탐색 과정

  1. a 노드(시작 노드)를 방문한다.
    • 방문한 노드는 방문했다고 표시한다.
  2. a와 인접한 노드들을 차례로 순회한다.
    • a와 인접한 노드가 없다면 종료한다.
  3. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다.
    • b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문한다.
  4. b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안된 정점을 찾는다.
    • 즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻이다.
    • 정점을 모두 방문했으면 종료한다.
    • 아직 방문이 안된 정점이 있으면 그 정점을 시작 정점으로 DFS를 시작한다.

DFS의 구현

  • 구현 방법은 2가지가 있다.
    1. 순환 호출 이용 즉, 재귀 함수 호출.
    2. 명시적인 스택 사용
      • 명시적인 스택을 사용하여 방문한 정점들을 스택에 저장하였다가 다시 꺼내어 작업한다.

만약 어떤 정점에서 더 방문할 노드가 없다면 자신을 불렀던 정점으로 돌아간다.
이 과정을 구현하기 위해 스택(Stack)을 사용한다.

방문하는 순서대로 정점을 스택에 쌓고, 방문이 끝나면 스택에서 pop하는 형태로 구현이 가능하다. 재귀 함수 또한 스택 메모리 공간에 쌓아 올려지는 구조를 띄므로 재귀 함수를 사용하여도 이것을 구현할 수 있다.

DFS의 시간 복잡도

  • DFS는 그래프(정점의 수:N, 간선의 수:E)의 모든 간선을 조회한다.
    • 인접 행렬로 표현된 그래프 : O(N^2)
      • 없는 간선도 저장한다.
    • 인접 리스트로 표현된 그래프 : O(N+E)
  • 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.
  • 보통은 E << N^2 이기 때문에 인접 리스트를 사용한다.

DFS 구현

  • 인접 리스트를 사용하여 구현한다.
  • 재귀 함수 호출을 사용한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.io.*;
import java.util.*;

/**
 * created by victory_woo on 02/04/2019
 * DFS와 BFS 복습
 */
public class BOJ1260_RE {
    private static final String SPACE = " ";
    private static ArrayList<Integer>[] a;
    private static boolean[] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(SPACE);
        int n = convert(input[0]); // 정점의 개수
        int m = convert(input[1]); // 간선의 개수
        int start = convert(input[2]); // 시작할 정점 번호

        // 배열 초기화.
        a = new ArrayList[n + 1];
        visit = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            a[i] = new ArrayList<>();
        }

        for (int j = 0; j < m; j++) {
            String[] inputs = br.readLine().split(SPACE);
            int u = convert(inputs[0]);
            int v = convert(inputs[1]);

            // 양방향 그래프일 경우 양쪽 다 추가해준다.
            a[u].add(v);
            a[v].add(u);
        }

        // 방문할 정점이 여러 개인 경우 정점 번호가 가장 작은 것부터 탐색하기 위해서 정렬한다.
        for (int i = 1; i <= n; i++) {
            Collections.sort(a[i]);
        }
        dfs(start);
    }

    private static int convert(String command) {
        return Integer.parseInt(command);
    }

    private static void dfs(int x) {
        // 방문한 적이 있다면 종료한다.
        if (visit[x]) {
            return;
        }

        visit[x] = true;
        // 방문한 순서 출력
        System.out.print(x+" ");

        for (int y : a[x]) {
            if (!visit[y]) {
                dfs(y);
            }
        }

    }
}
입력
5 4 5
5 4
4 3
4 2
1 5
출력 결과
5 1 4 2 3

참고