DFS와 BFS의 시각화 비교

연습 문제를 풀다 보면 DFS(깊이 우선 탐색)를 쓸지, BFS(너비 우선 탐색)를 쓸지 결정하는 것이 항상 간단한 일은 아닙니다. 알고리즘의 기본 원리를 이해했다고 하더라도, 실제 상황에서는 그 선택이 문제의 본질과 직접적으로 연결되기 때문입니다.

이런 고민 끝에, DFS와 BFS를 직접 시각화해서 그 차이를 직관적으로 비교해보기로 했습니다.

해당 시각화는 120x120 크기의 장애물 없는 격자에서 DFS와 BFS를 시작 지점 (0, 0)으로부터 실행하고, 그 탐색 경과를 .bmp 이미지로 저장한 것입니다. 시각화 소스 코드는 맨 아래에 첨부한 GitHub 저장소에서 확인할 수 있습니다.

DFS (Depth-First Search)

DFS는 말 그대로 “깊이 우선” 탐색입니다. 가능한 한 깊게 탐색한 뒤, 더 이상 탐색할 노드가 없을 경우에야 되돌아옵니다. 이는 일종의 백트래킹 구조를 띠며, 재귀적으로 다음 노드를 따라 내려가는 방식입니다.

예제 레포지토리 내의 DFS 코드는 다음과 같습니다. DFS/BFS 모두 bmp_class.cpp에 정의되어 있고 bitmap 클래스 안의 메서드입니다.

    void dfs(int row, int col, int depth) {
        if(!is_avail(row,col)) return;
        visited[row][col] = true;
        image_data[row][col].color(depth);
        int drow[] = {-1,1,0,0};
        int dcol[] = {0,0,-1,1};
        for(int i = 0; i < 4; i++) {
            int nrow = row+drow[i], ncol = col+dcol[i];
            if(is_avail(nrow,ncol)) {
                dfs(nrow,ncol,depth+CNT);
            }
        }
    }

이와 같이 재귀 깊이와 다음 순회 위치룰 주면서 코드가 진행됩니다.

image_data[row][col].color(depth); 구문이 실행될 때 이미지 상에서 색상이 깊이에 따라 변화하며, 실제로 깊은 영역일수록 색이 변화된 것을 볼 수 있습니다. 탐색이 한 방향으로 깊게 진행되다 보니, 일부 영역이 빠르게 깊은 색상(청록 등)으로 채색됩니다. 이는 탐색 깊이에 따라 색상이 다음과 같이 표현되었기 때문입니다:

• 검정 → 파랑 → 청록

이는 .bmp의 픽셀 단위가 RGB 순서(Blue → Green → Red)로 저장되기 때문이며, DFS의 재귀 깊이를 시각화하기 적절한 방법입니다.

위 이미지: DFS의 탐색 결과. 깊게 찌르듯 한쪽으로 파고드는 경향이 보인다.

이러한 방식은 특정 노드까지의 최단 거리를 구하는 데에는 적합하지 않습니다. DFS는 경로의 깊이만을 추적하며, 경로의 효율성이나 최소성에는 관여하지 않기 때문입니다.

BFS (Breadth-First Search)

BFS는 시작 지점으로부터 일정 거리를 두고 넓게 퍼져나가는 방식으로 탐색합니다. 가장 가까운 노드부터 순차적으로 처리하기 때문에, 특정 노드까지의 최소 이동 횟수를 계산하는 데 매우 유리합니다.

   void bfs(int row, int col) {
        std::queue<pair<int,int>> q;
        q.push(make_pair(row,col));
        image_data[row][col].color(0);
        while(q.size()) {
            pair<int,int> point = q.front();
            int cur_row = point.first, cur_col = point.second;
            visited[cur_row][cur_col] = true;
            int cur_color = image_data[cur_row][cur_col].get_color();
            q.pop();
            int drow[] = {-1,1,0,0};
            int dcol[] = {0,0,-1,1};
            for(int i = 0; i < 4; i++) {
                int nrow = drow[i]+cur_row, ncol = dcol[i]+cur_col;
                if(is_avail(nrow,ncol)) {
                    visited[nrow][ncol] = true;
                    q.push(make_pair(nrow,ncol));
                    image_data[nrow][ncol].color(cur_color+CNT);
                }
            }
        }
    }

이 BFS 구현에서는 큐와 적절한 방문처리를 통해 격자를 순회하고, CNT만큼 증감하며 픽셀 색상의 변화를 유도하였습니다.

달리 말해 (0,0)에서부터의 거리 값에 따라 픽셀 색상을 채우도록 시각화한 것입니다. 결과적으로, 중심부에서 시작해 바깥쪽으로 부드럽게 색이 짙어지는 그래프가 생성됩니다.

위 이미지: BFS의 탐색 결과. 거리 기반 채색 덕분에 부드럽게 번지는 패턴을 보인다.

BFS는 명확하게 거리 기반 탐색이 필요한 상황(최단 경로 탐색, 거리 측정 등)에 매우 적합하며, DFS와는 상반된 특성을 가집니다. 완전탐색을 위한 백트래킹 기법 등은 재귀 깊이가 깊지 않다면 보다 간소한 DFS를 사용하는 것도 좋은 방법입니다.

결론

DFS와 BFS는 각각 장단점이 뚜렷하며, 쓰임새도 명확히 구분됩니다.

텍스트만으로 이해하기 어려운 DFS와 BFS의 차이를 이미지로 시각화하면, 두 탐색 알고리즘의 특성과 용도를 보다 명확히 구분할 수 있습니다.

참고 저장소 GitHub: traverse_visualization_bmp