깊이 우선 탐색(DFS: Depth-First Search)에 대해 알아보자

지난번 포스팅으로 정렬 부분 정리가 끝나고 이제 탐색에 관한 부분이다. 탐색의 방법은 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)으로 나누어진다. 이것을 이해하기 위해서는 트리구조를 알고 있어야 한다. 루트로부터 탐색을 시작하여 깊이가 증가하는 방향으로 쭉 리프까지 탐색을 하는 것이 DFS이고 하나의 노드에서 모든 자식들을 탐색하고 다음 깊이로 넘어가는 것이 BFS이다. 이번에는 DFS를 먼저 살펴보고 다음에 BFS를 알아보도록 하겠다.

DFS는 스택, 재귀함수와 관련이 아주 깊다. 깊이가 증가하며 탐색하는 것이 함수를 반복적으로 호출하는 것으로 구현할 수 있기도 하고 스택의 후입선출 특성과 맞아떨어지기 때문이다. 다음 그림을 보자.

간간한 트리 형태로 예제를 들어보겠다. DFS는 4-2-1-3-6-5-7 순서로 탐색하는 것을 의미한다. 가장 먼저 루트를 탐색하고 루트의 자식을 탐색하되, 해당 자식 노드의 자식을 바로 탐색하여 리프까지 탐색한 후 더이상 자식이 없을 때 부모노드로 올라가 다른 자식노드를 탐색하는 것이다. 여기서 스택구조를 볼 수 있는데 자식 노드가 존재하면 스택에 넣고 탐색하면서 스택에서 빼면서 탐색한다고 해보자. 먼저 루트인 4를 스택에 넣는다. 그리고 바로 4를 빼면서 자식 노드를 찾는다. 2와 6이 있으므로 큰 수부터 넣어 6, 2를 넣는다. 더 이상 자식노드가 없으므로 2를 빼고 2의 자식 노드인 3과 1을 넣는다. 여기까지 보면 스택의 밑부분부터 6,3,1 순으로 쌓인 것을 볼 수 있다. 스택은 후입선출이므로 현재 노드의 작은 숫자의 자식 노드부터 탐색이 이루어짐을 알 수 있다.

하지만 실제 DFS를 구현할때는 스택보다는 재귀함수를 사용하는 편이다. 재귀함수도 스택의 성질을 일부 가지고 있기 때문이다. 또한 트리구조에서는 중복 방문이 일어날 수 없지만 그래프에서는 중복 방문이 빈번하게 일어나고 이것을 막아주지 않는다면 시간이 많이 걸리는 경우가 있다. 따라서 방문여부를 확인할 배열을 빠로 선언하여 재귀호출시마다 체크해주어야 한다. DFS의 시간복잡도는 노드와 에지의 수를 더한 것이다. 실제 문제를 풀 때는 DFS자체의 시간복잡도보다는 구현 방식에 의한 시간이 영향을 더 크게 미치는 편이다. 탐색뿐만 아니라 주어진 노드 간의 연결관계를 저장하는 방식에 따라서도 시간차이가 크게 벌어진다. 노드의 관계는 주로 ArrayList를 이용하거나 2차원배열을 이용한다. 탐색 시에는 ArrayList가 더 유리한 측면이 있다. 직접적인 구현은 여러 포스팅에 걸쳐 문제를 풀며 알아보도록 하자. 이번에는 기본적인 코드만 살펴보도록 하겠다.

백준 11724번을 이용하였다. https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

그래프에서 서로 연결되어있는 노드들이 몇 덩어리 있는지 묻는 문제이다.

import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<Integer>[] array;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        array = new ArrayList[N+1];
        visited = new boolean[N+1];
        for(int i=1;i<=N;i++){
            array[i] = new ArrayList<Integer>();
        }
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            array[a].add(b);
            array[b].add(a);
        }
        int cnt = 0;
        for(int i=1;i<=N;i++){
            if(visited[i]) continue;
            visit(i);
            cnt++;
        }
        bw.write(cnt+"");
        bw.flush();
        bw.close();
    }
    static void visit(int node){
        visited[node] = true;
        for(int i:array[node]){
            if(!visited[i]) {
                visit(i);
            }
        }
    }
}

visit이라는 함수를 선언해 재귀함수로 구현하였다. 모든 노드를 검색하며 방문해 준 노드들을 방문표시를 해 주고 연결된 노드들까지 전부 방문해 준 다음, 방문하지 않은 노드를 찾아 작업을 반복해 준다. 그리고 카운트변수를 그때마다 추가해 주면 된다.