[Algorithm] DFS와 BFS (with stack/queue)

DFS

 

 스택(재귀)을 이용한 DFS에 대하여 알아보자.  코드의 편하게 작성하기 위해서 DFS는 스택을 따로 만들지 않고 재귀적으로 구현하기도 하는데, 이는 재귀적으로 함수호출이 이루어지는 로컬공간 자체가 스택의 구조를 갖고 있기 때문에 동일한 원리라고 할 수 있다.

//백트래킹
void dfs(int root) {
    if(종료조건) return;
    for(i: root에 방문하지 않은 자식노드) {
        dfs(i);
}

 

재귀를 이용한 DFS는 간단하게 종료조건이 나오기 전까지 계속 재귀호출을 이어가다가, 종료조건이 나오면 return하는 방식의 DFS이다.

 

스택을 사용한 DFS도 원리는 동일하다. 다만 상태공간트리에서 leaf노드를 나타낼 때 재귀를 이용한 구현에서는 return문을 사용했다면, 스택을 이용한 구현에서는 스택의 원소 하나를 스택에서 제거하면 된다. 간단하게 설명하면 이렇다.

0. 스택에 시작(루트)노드를 넣는다
1. 스택의 최상단 노드를 확인(peek)한다.
2. 최상단 노드에 방문하지 않은 인접 노드가 있다면, 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없다면, 스택에서 최상단 노드를 제거(pop)한다

 

1번과 2번의 과정을 스택에 아무런 노드가 없을 때까지 반복하면 된다.

 

// 재귀
void dfs(int depth) {
  visited[depth] = true;
  for(해당 노드와 연결되어 있는 노드 newnode들 && !visited[newnode]) {
    dfs(newnode);
  }
}

//스택
void dfs(int root) {
    visited[root]=true;
    while(!stack.isEmpty()) {
        int node = stack.peek();
        if(!visited[i:node의 인접노드]) {
            stack.push(i)
            visited[i]=true;
        }
        else { //인접노드가 존재하지않거나 모두 방문했다면
            stack.pop();
        }
    }
}

 

 

 

BFS

 

DFS는 스택을 이용했다면, 큐를 이용하면 BFS를 구현할 수 있다. DFS와의 가장 큰 차이는 재귀적으로 동작하지 않는다는 점이다.

 

0. 큐에 시작(루트)노드를 넣는다.
1. 큐의 head에 위치한 노드를 확인 후 제거(dequeue)한다.
2. 확인한 노드와 인접한 모든 노드들을 큐에 넣는다.

역시 큐에 아무런 노드가 없을때까지 1, 2번을 반복하면 된다. 원리를 정확히 이해하고 있다면 DFS보다 더 직관적으로 이해할 수 있다. 

void bfs(int root) {
    visited[root]=true;
    while(!queue.isEmpty()) {
        int node = queue.dequeue();
        for(i: node의 인접노드 && !visited[i]) {
            queue.enqueue(i);
        }
    }
}

void bfs(int root) {
    while(!queue.isEmpty()) {
        int node = queue.dequeue();
        for(i: node의 인접노드 && !visited[i]) {
            queue.enqueue(i);
            visited[root]=true;
        }
    }
}

- 위 두 코드는 방문처리를 하는 시점에서 차이를 보인다. 둘 다 결과는 똑같으나, 전자의 방법으로 탐색하게 되면 방문할 예정이라 이미 큐에 들어가있는 노드가 다시 큐에 들어가서 불필요한 메모리와 시간을 차지할 수 있기 때문에 후자의 방법이 훨씬 효율적이라고 할 수 있다. (헷갈린다면 BOJ 2636 메모리초과가 난 코드를 보자 - https://www.acmicpc.net/source/64076941과 https://www.acmicpc.net/source/64077141)

 

- bfs의 특징 중에 하나는 가중치가 모두 동일하다면 탐색순서가 최단거리를 보장한다는 사실이다. 가중치가 같은 문제라면 bfs를 고려해볼 만 하다.

 

- c와 같이 큐 라이브러리가 존재하지 않을 경우, 링크드 리스트를 이용하여 리스트에 추가시키는 방식으로 재귀적으로 구현할 수 있다. (c 파일탐색 github 참고)

 

- dfs와 bfs 모두 O(v+e)의 시간복잡도를 가지지만, 일반적으로 속도는 bfs가 dfs보다 더 빠르다고 알려져있다. 그런데 이것이 단순히 큐와 스택의 속도 차이 때문인지, 아니면 dfs의 방식이 한쪽 가지로 깊게 탐색하다보니 location depth에 따른 효율이 떨어지기 때문인지는 잘 모르겠다.

 

 

 

BOJ 1260) DFS, BFS 구현 예시

import java.util.*;

public class Main {

    static int N;
    static int M;
    static int V;
    static LinkedList[] adList; //인접 리스트


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        V = sc.nextInt();

        adList = new LinkedList[N+1];

        for(int i=1; i<=N; i++)
            adList[i] = new LinkedList<>();


        for(int i=0; i<M; i++) {
            int n1 = sc.nextInt();
            int n2 = sc.nextInt();
            //양방향 관계 설정
            adList[n1].add(n2);
            adList[n2].add(n1);
        }

        for(int i=1; i<=N; i++)
            Collections.sort(adList[i]);

        dfs(V);
        System.out.println();
        bfs(V);


    }

    private static void dfs(int root) {
        boolean[] visited = new boolean[N+1];

        Stack<Integer> stack = new Stack<>();
        stack.push(root);
        visited[root] = true;
        System.out.print(root + " ");

        while(!stack.isEmpty()) {
            int node = stack.peek(); //스택 최상단의 노드를 확인한다.
            boolean flag = false;

            for(int i=0; i<adList[node].size(); i++) {
                int v = (int)adList[node].get(i);
                if(!visited[v]) { //아직 방문하지 않은 노드가 있다면
                    stack.push(v); //그 노드를 스택에 넣어주고
                    visited[v] = true; //방문표시를 해준다.
                    flag = true;
                    System.out.print(v + " ");
                    break;
                }
            }
            if(!flag)
                stack.pop();
        }

    }

    private static void bfs(int root) {
        boolean[] visited = new boolean[N+1];

        Queue<Integer> queue = new LinkedList<>();
        queue.add(root);
        visited[root] = true;
        System.out.print(root + " ");

        while(!queue.isEmpty()) {
            int node = queue.remove();
            for(int i=0; i<adList[node].size(); i++) {
                int v = (int)adList[node].get(i);
                if(!visited[v]) {
                    queue.add(v);
                    visited[v] = true;
                    System.out.print(v + " ");
                }
            }
        }
    }
}

 

 

시간복잡도

 컴퓨터는 간단한 동작을 1초에 1억 번 한다. 간단하게 시간 limit이 1초라면, O(n^2) 알고리즘을 사용하여 해결할 수 있는 n은 5000정도, O(nlogn) 알고리즘을 사용하여 해결할 수 있는 최대 n은 20만 정도다. 

DFS는 인접행렬의 경우 O(V^2), 인접 리스트의 경우 O(V+E)정도의 시간복잡도를 가진다.

일반적으로 분기가 2개로 나뉘는 탐색문제를 생각해보면, 2^27이 1억 3~4천 정도로 n=26~27정도가 메모이제이션 없는 brute force dfs로 해결할 수 있는 마지노선이라고 생각하면 되겠다.