깊이 우선 탐색DFS(Depth-First_Search)

지난 번에 그래프의 종류에 대해서 정리를 했다. 오늘은 그래프를 순회하는 방법중의 하나인 DFS탐색법을 정리하겠다. BFS는 다음시간에 이어서 정리하도록 하겠다. 코테에 가장 많이 나오는 탐색유형으로 한 번쯤은 정리할 필요성이 있다고 생각했다. 

아직 그래프에 대해 잘 모른다면, 여기로 가서 간단하게 개념을 익히고 오는 것이 좋을 것 같다.

보통 BFS는 큐를, DFS는 스택을 사용하여 구현하는데, 재귀함수 또한 스택 메모리 공간에 쌓아 올려지는 구조를 띄기 때문에 재귀함수를 사용하여 구현 및 정리하도록 하겠다.

그래프의 모든 정점을 한 번씩만 방문하기 위해 DFS(depth-first-search)를 구현하기 전에 간단하게 DFS의 탐색 과정과 순서를 살펴보고 넘어가자. 이름 그대로 한 우물만 깊게 파다가 막히면 그제서야 뒤로 돌아가서 다른 우물을 파는 성질이 있다. 쉽게 말하면 방문할 수 있는 곳이 하나라도 있다면 주체가 바뀌면서 계속 밑으로 뚫고 내려간다. 주체가 바뀐다는 말이 애매하지만, 사진과 함께 보면 이해하기가 어렵지 않을 것이다.

아래와 같은 연결그래프가 있다고 해보자. 방금 막 방문한 지점을 빨간색, 이전에 방문한 노드를 초록색, 아직 방문하지 않은 노드를 파란색으로 표현해 나가면서 탐색의 진행을 보도록 하겠다.

일단 맨 처음 방문한 0번 노드의 인접 노드는 1, 2번 노드가 있다. 이 중에서 더 작은 노드 1번 노드를 방문한다고 하자. 여기서 순서는 중요하지 않다. 인접노드에 대한 방문 순서가 특정하게 정해진 것이 아니라면 보통 왼쪽 자식으로 먼저 간다.

자, 그러면 이제 여기서 0번 노드의 다른 인접 노드인 2번 노드를 방문하는 것이 아니라, 1번 노드의 인접노드를 방문한다. 이것이 필자가 위에서 말한 주체가 바뀐다는 뜻이다. 1번 노드의 인접노드 0, 3, 5중에서 0은 이미 방문했기 때문에 3번과 5번 노드 중에서 왼쪽인 3번 노드를 방문한다.

 

이 다음에는 1번은 이미 방문했으니 고민할 것도 없이 4번 노드를 방문합니다.

 

마찬가지로 현재 방문한 4번 노드에서는 더이상 방문할 곳이 5번 뿐이므로 고민도 없이 5번 노드를 방문합니다.

여기서부터가 중요하다. 5번노드와 인접한 노드는 모두 방문했기 때문에 더 이상 방문할 노드가 없다. 이때는 자신을 호출한 이전 노드로 되돌아가서 아직 방문한 적이 없는 노드를 방문해야 한다.  4번에서도 더이상 방문할 노드가 없다면 또 자신을 호출한 3번 노드로 돌아가는 과정을 반복한다. 5 -> 4 -> 3 -> 1 -> 0. 0번 노드로 다시 돌아와서야 인접 노드중 아직 방문하지 않은 2번 노드를 방문한다. 

 

여기서부터는 앞에서와 마찬가지로 인접한 노드 중에서 더 작은 노드를 기준으로 방문한다. 2번 노드는 6번을 호출해서 방문할 것이다.

6번 정점은 이어서 7번 정점을 호출해서 7번을 방문한다. 여기서, 또 7번 노드에서는 인접 노드 중에서 방문할 곳이 없기때문에 6번 노드로 돌아가서 6번 노드의 아직 방문하지 않은 인접 노드인 8번 노드를 방문한다.

8번 정점을 방문하고 나면 아무리 뒤로 돌아가도 더 이상 방문할 수 있는 정점이 없다. 이러면 탐색이 종료된 것이고, 0번 노드와 직/간접적으로 연결되어 있는 모든 노드를 탐색한 것이다. 

그렇다면 위의 과정을 코드로 직접 구현한 코드를 살펴보자. 필자는 재귀함수를 사용한다고 했다. 전체 소스코드를 첨부하고 하나씩 잘라서 세부적으로 살펴보자

package DFS;
 
import java.util.ArrayList;
import java.util.List;
 
public class DFS방문예제 {
    static List<ArrayList<Integer>> injacList;
    static boolean visit[];
    static StringBuilder sb = new StringBuilder();
    static int cnt = 1;
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        
        //그래프에 대한 정보
        int node = 9;
        int edge = 10;
        List<Node> GList = new ArrayList<>(edge);
        GList.add(new Node(0, 1));
        GList.add(new Node(0, 2));
        GList.add(new Node(1, 3));
        GList.add(new Node(1, 5));
        GList.add(new Node(2, 6));
        GList.add(new Node(2, 8));
        GList.add(new Node(3, 4));
        GList.add(new Node(4, 5));
        GList.add(new Node(6, 7));
        GList.add(new Node(7, 8));
        
        //인접 리스트 생성하기 
        injacList = new ArrayList<ArrayList<Integer>>(node);
        
        for(int i=0; i<node; i++) {
            injacList.add(new ArrayList<Integer>());
        }
        
        for(int i=0; i<edge; i++) {
            Node n = GList.get(i);
            injacList.get(n.from).add(n.to);
            injacList.get(n.to).add(n.from);
        }
        
        visit = new boolean[node];
        
        //시작노드 0번부터 시작
        sb.append("round 1 : node 0 visited").append('\n');
        dfs(0);
        
        System.out.println(sb.toString());
    }
    
    private static void dfs(int start) {
        // TODO Auto-generated method stub
        visit[start] = true;
        
        for(int num : injacList.get(start)) {
            if(!visit[num]) {
                visit[num] = true;
                sb.append(String.format("round %d : node %d visited\n", ++cnt, num));
                dfs(num);
            }
        }
    }
 
    static class Node{
        int from, to;
 
        public Node(int vertex, int link) {
            super();
            this.from = vertex;
            this.to = link;
        }
    }
}

1. [ 그래프의 정보 ]

15~27행을 먼저 보자. 이는 필자가 위에서 DFS의 탐색 과정을 설명한 예시 그래프를 코드상에서 구현하기 위해 표현한 그래프의 정보이다. 여기까지 정리를 읽으면서 따라왔다면, 어느 순서로 방문하는지는 알았을텐데, 코드로는 어떻게 구현하는지 그리고 예시와 정말 같은 순서로 방문하는지 확인해보자.

2. [ 인접리스트 생성 ]

30~40행을 보자. 그래프의 정보를 기반으로 인접리스트를 구현했다. 리스트 2개를 중첩한 구조로, 예를 들어 injacList.get(3)은 3번 노드와 연결된 즉, 인접한 노드들을 arrayList에 담아서 연결한 것이다. 중요한 것은 현재 그래프가 방향이 없는 그래프이기 때문에 양방향으로 인접리스트에 초기화해야 한다. 

3 [ 깊이 우선 탐색 ]

51행부터 이어지는 dfs메소드를 보자. 개선루프를 사용하여 현재 노드와 연결된 인접 노드를 탐색한다. 인접노드가 아직 방문하지 않은 상태라면 방문체크를 하고 깊이를 더 내려가서 탐색을 진행한다. 위의 코드의 결과는 아래와 같다. round는 방문 순서를 나타낸 것이고 그 뒤는 그 순서에 방문한 노드를 출력한 것이다. 위의 예시와 동일한 순서로 방문한 것을 확인할 수 있다. 방문순서는 인접리스트에 add하는 순서 혹은 정렬 상태에 의해 충분히 다르게 나올수 있고, 아래는 기본적인 예시인 것으로 오늘은 DFS가 어떤방식으로 탐색을 하는가? 그리고 어떻게 구현하는가?를 확실히 정리하고 넘어가자.

자, 위의 예시는 모든 노드가 연결되어 있었다. 그렇다면 직/간접적으로 연결되지 않은 노드는 어떨까? 단순하게 생각해도 당연히 방문할 수 없는데 맞다. 그래프 용어 중에 하나로 연결요소(component)라는 게 있다고 했다. 컴포넌트 하나 안에 속한 정점은 서로 모두 이어져 있고, 다른 컴포넌트끼리는 이어져 있지 않다. 또한 하나의 컴포넌트는 항상 최대 크기를 유지해야 한다. 

하나의 예시로 아래와 같은 그림을 보자. 밑의 그림은 총 3개의 컴포넌트가 존재하는 경우이다. 같은 색의 정점들끼리 하나의 컴포넌트를 이루는 경우이다. 그렇다면 필자가 예시로 들었던 무방향 연결그래프는 컴포넌트가 몇개일까? 맞다 1개다.

 

따라서, 컴포넌트가 2개 이상인 경우에 모든 정점을 방문하기 위해서는 각 컴포넌트에 속한 정점들 중 하나씩은 방문 시도를 해줘야 하고, 이를 구현하는 가장 쉬운 방법은 반복문을 돌면서 방문하지 않은 정점을 볼 때마다 DFS를 시작해주는 것입니다. 이때, 방문을 시도하는 횟수가 컴포넌트의 개수가 된다.

그렇다면 아래와 같은 그래프를 방문해보는 실습을 해보겠습니다. 보면 알겠지만, 같은 색끼리 하나의 컴포넌트다.

package DFS;
 
import java.util.ArrayList;
import java.util.List;
 
public class DFS방문예제_component {
    static List<ArrayList<Integer>> injacList;
    static boolean visit[];
    static StringBuilder sb = new StringBuilder();
    static int component;
    static int cnt = 0;
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        
        //그래프에 대한 정보
        int node = 10;
        int edge = 7;
        List<Node> GList = new ArrayList<>(edge);
        GList.add(new Node(0, 1));
        GList.add(new Node(1, 3));
        GList.add(new Node(2, 3));
        GList.add(new Node(4, 6));
        GList.add(new Node(5, 7));
        GList.add(new Node(5, 8));
        GList.add(new Node(7, 8));
        
        //인접 리스트 생성하기 
        injacList = new ArrayList<ArrayList<Integer>>(node);
        
        for(int i=0; i<node; i++) {
            injacList.add(new ArrayList<Integer>());
        }
        
        for(int i=0; i<edge; i++) {
            Node n = GList.get(i);
            injacList.get(n.from).add(n.to);
            injacList.get(n.to).add(n.from);
        }
        
        visit = new boolean[node];
        
        
        for(int i=0; i<node; i++) {
            if(!visit[i]) {
                cnt = 0;
                sb.append("---새로운 컴포넌트 발견! DFS 탐색 시작---").append('\n');
                sb.append(String.format("round %d : node %d visited\n",++cnt, i));
                component++;
                dfs(i);
            }
        }
        System.out.println(sb.toString());
        System.out.println("컴포넌트(연결요소)의 개수는 " + component);
    }
    
    private static void dfs(int start) {
        // TODO Auto-generated method stub
        visit[start] = true;
        
        for(int num : injacList.get(start)) {
            if(!visit[num]) {
                visit[num] = true;
                sb.append(String.format("round %d : node %d visited\n", ++cnt, num));
                dfs(num);
            }
        }
    }
 
    static class Node{
        int from, to;
 
        public Node(int vertex, int link) {
            super();
            this.from = vertex;
            this.to = link;
        }
    }
}
 
 

 

마지막으로 DFS의 시간복잡도를 살펴보자. 

결론적으로 말하면 정점과 간선의 개수합인 O(V+E)이다. 이는 한 번 방문한 정점은 다시 방문하지 않으며, 한 정점에서 다음으로 방문할 노드들을 순회하는 횟수가 그 정점의 차수(연결된 인접노드의 수)와 같기 때문이다.

이번 시간에는 DFS의 기본예제를 살펴보았다. 이것이 모든 DFS를 표현할 수 있는 것이 아니고, 경우에 따라서 즉, 그래프의 종류에 따라서 탐색하는 순서도 다르고, 이 후에 배울 다양한 알고리즘의 기본도구로 사용되는 등,,, 어렵다.   따라서   기본 예시를 참조하여 많은 연습이 필요할 것이다.