6. DFS와 BFS

깊이 우선 탐색(DFS: Depth First Search)과 너비 우선 탐색(BFS: Breadth First Search)는 탐색방법 중 가장 기본이 되는 방식입니다. 이름에 어떠한 방식으로 탐색이 이루어지는지 압축적으로 제시된 것만큼 그 사용목적과 방법이 확실한 알고리즘이라고 할 수 있습니다.

DFS는 말그대로 깊이를 우선하여 탐색하는 알고리즘입니다. 만일 격자 모양으로 구성된 하나의 그래프가 주어졌다고 생각해보겠습니다. 중간에 끊김없이 한칸한칸을 모두다 탐색해야한다고 했을 때 우리가 취할 수 있는 방법은 마치 한 손 그림을 그리듯 쭉 타고 가면서 하나씩 노드들을 방문하는 것입니다. 오른쪽으로 쭉타고 가다가 더이상 오른쪽으로 갈 수 없으면 밑으로 그리고 더이상 밑으로 갈 수 없으면 왼쪽으로 또 더이상 왼쪽으로 갈 수 없게되면 위쪽으로... 이렇게 마치 달팽이 그리듯 타고 가다보면 모든 모드들을 빠짐없이 탐색할 수 있을 것입니다. 만일 중간에 길이 막혀 더이상 갈 수 없는 곳이 생기면 최대한 가까운 곳에서 다시 탐색을 시작하는 방식으로 탐색을 이어나갈 수 있을 것입니다. 이처럼 중간에 나올 수 있는 다른 루트들을 고려하지 않고 일차적으로 자신이 갈 수 있는 경로 중에 하나를 선택하여 최대한 깊이깊이 탐색하는 것이 DFS의 본질이라고 할 수 있습니다.

그에 반해서 BFS는 노드에서 자신이 갈 수 있는 모든 경로에 대해 계속적으로 탐색하면서 나아가는 점진적 방식의 알고리즘입니다. 시작점에서 갈 수 있는 모든 경로 정보를 체크하면서 특정 노드에 접근이 가능한지를 확인하고, 그 노드에 접근이 가능하다면 그 노드를 다음 탐색후보로 등록하게 됩니다. 그리고 그 탐색후보 노드에서 또 다시 접근 가능한 노드들을 확인하고 그 노드들을 후보노드로 등록하는 반복적인 작업을 통해 갈 수 있는 모든 노드들을 탐색하는 것입니다.

저는 일반적으로 DFS와 BFS를 설명할 때 하나의 예시를 들고는 합니다. 탐험에 나선 한 사람이 있다고 상상해봅시다. 누군가의 도움을 얻을 수 없을 때, 그 사람은 자신이 갈 수 있는 길을 따라서 최대한 많이 가보려고 할 것입니다. 그리고 그렇게 다 가보고 나서 길이 끊기거나 막혀서 갈 수 없게 되었을 때 다시 길을 빠져나오다가 자신이 갈 수 있는 다른 길을 발견하면 다시 그 길을 또 탐색하려고 할 것입니다. 이 예시가 DFS를 단적으로 잘 설명해준다고 할 수 있습니다. 그에 반하여 BFS는 일단 한번 움직여서 가볼 수 있는 지역을 모두 탐색한 뒤 기록해두는 방식입니다. 그다음 한번 움직여서 방문한 지역정보를 바탕으로 다시 또 한번 갈 수 있는 지역들을 탐색하면서 기록하는 것입니다. 이렇게 퍼져나가듯이 탐색하는 것이 BFS라고 할 수 있습니다. 이 예시들이 DFS와 BFS를 직관적으로 이해하는데 도움이 되셨기를 바랍니다.

깊이 우선 탐색(DFS: Depth First Search)

package DFSTest;
 
public class DFSTest {
    // 움직일 수 있는 네 방향은 미리 배열로 선언해두면
    // 나중에 for문을 이용하여 탐색하기 편합니다.
    // 방문순서는 상우하좌의 순서로 방문하도록 세팅되었습니다.
    private static int[] addRow = { -1, 0, 1, 0 };
    private static int[] addCol = { 0, 1, 0, -1 };
    private static int[][] map;
    private static int cnt;
 
    public static void main(String[] args) {
        // DFS를 테스트할 2차원 배열을 생성합니다.
        // 배열을 최초 생성할 경우 배열 안의 값은 모두 0으로 초기화되어있습니다.
        map = new int[10][10];
 
        // dfs 작업은 함수를 따로 빼서 진행하겠습니다.
        // 탐색의 시작점은 좌표 (0, 0) 입니다.
        // 몇 번째로 방문했는지 확인하기 위해 cnt변수를 이용하여 방문순서를 세어보겠습니다.
        cnt = 1;
        dfs(0, 0);
 
        // 어떤 순서로 방문되었는지 직접 프린트해보면서 설명을 마치겠습니다.
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }
 
    // row, col은 현재 위치가 됩니다.
    private static void dfs(int row, int col) {
        // map에서 방문한 곳은 cnt값을 부여하고 그 값을 하나 더해줍니다.
        map[row][col] = cnt++;
        for (int i = 0; i < 4; i++) {
            // 다음 위치는 nextRow와 nextCol값으로 상정합니다.
            int nextRow = row + addRow[i];
            int nextCol = col + addCol[i];
            // 만일 map에서 방문한 곳이어서 0보다 큰 값을 가지고 있으면 넘어갑니다.
            // 재방문을 막는 것입니다.
            // 만일 이동하려는 좌표가 우리가 선언한 2차원 배열을 넘어서면 안되기 때문에
            // 사이즈를 0에서 선언된 배열의 크기로 제한해줍니다.
            if (nextRow < 0 || nextRow >= map.length || nextCol < 0 || nextCol >= map[nextRow].length
                    || map[nextRow][nextCol] > 0)
                continue;
            // 만일 값을 갖지 않고 있다고 재귀함수를 이용하여 dfs를 다시 호출하고,
            // 다음 위치를 탐색하도록 합니다.
            dfs(nextRow, nextCol);
        }
        // 만일 더이상 탐색할 곳이 남아있지 않게 된다면 함수는 자동적으로 종료될 것입니다.
    }
}
 

너비 우선 탐색(BFS: Breadth First Search)

import java.util.LinkedList;
import java.util.Queue;
 
public class BFSTest {
    // 움직일 수 있는 네 방향은 미리 배열로 선언해두면
    // 나중에 for문을 이용하여 탐색하기 편합니다.
    // 방문순서는 상우하좌의 순서로 방문하도록 세팅되었습니다.
    private static int[] addRow = { -1, 0, 1, 0 };
    private static int[] addCol = { 0, 1, 0, -1 };
    private static int cnt;
 
    public static void main(String[] args) {
        // BFS를 테스트할 2차원 배열을 생성합니다.
        // 배열을 최초 생성할 경우 배열 안의 값은 모두 0으로 초기화되어있습니다.
        int[][] map = new int[10][10];
 
        // BFS 작업을 위한 Queue를 하나 선언합니다.
        // DFS와 마찬가지로 탐색의 시작점은 좌표 (0, 0) 입니다.
        // 몇 번째로 방문했는지 확인하기 위해 cnt변수를 이용하여 방문순서를 세어보겠습니다.
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(new Node(0, 0));
        cnt = 1;
 
        // while 문을 돌면서 Queue가 빌때까지 map의 좌표를 방문하면서 탐색합니다.
        while (!queue.isEmpty()) {
            // Queue에는 탐색 후보노드 정보가 들어있습니다.
            // 하나씩 poll해서 탐색합니다.
            Node node = queue.poll();
 
            // poll해서 얻을  Node객체에서 row와 column 정보를 가져옵니다.
            int row = node.row;
            int col = node.col;
 
            // 이미 탐색된 좌표는 continue로 넘어갑니다.
            if (map[row][col] > 0)
                continue;
 
            // 탐색되지 않은 좌표에는 탐색되었다는 의미에서 cnt값을 부여합니다.
            map[row][col] = cnt++;
            // 네 방향을 for문을 이용해서 탐색합니다.
            for (int i = 0; i < 4; i++) {
                // 다음으로 방문할 좌표는 nextRow와 nextCol입니다.
                int nextRow = row + addRow[i];
                int nextCol = col + addCol[i];
                // 우리가 탐색하려는 map배열 사이즈 안에 들어가는지 확인해봅니다.
                if (nextRow < 0 || nextRow >= map.length || nextCol < 0 || nextCol >= map[nextRow].length
                        // 이미 방문한 좌표라면 굳이 후보노드로 등록할 필요가 없으므로 필터링할 조건에 추가해줍니다.
                        || map[nextRow][nextCol] > 0)
                    continue;
                // 위의 필터링 조건에 걸리지 않았다면 후보노드로서 자격이 있으므로 Queue에 추가해줍니다.
                queue.add(new Node(row + addRow[i], col + addCol[i]));
            }
        }
 
        // 마지막으로 탐색된 순서를 확인해주기 위해서 프린트해줍니다.
        // 마치 물결이 퍼져나가듯 탐색되었다는 것을 확인할 수 있습니다.
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }
}
 
// Node의 정보를 저장해줄 class를 하나 선언해줍니다.
// 2차원 배열이므로 좌표값은 row, column 두가지가 생깁니다.
// row는 row로 column은 col로 변수명을 주었습니다.
class Node {
    int row;
    int col;
 
    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }
}