BFS(너비 우선 탐색)란?

BFS(Breadth-First Search)는 그래프 또는 2차원 배열에서 가까운 곳부터 차례로 탐색하는 알고리즘이다.
트리, 미로, 게임 맵과 같이 모든 경로를 탐색하거나 최단 경로를 찾는 문제에 자주 사용된다.
BFS는 한 노드에서 시작해 인접한 노드들을 먼저 방문한 후, 그 다음 깊이의 노드들을 탐색해 나간다.

BFS 특징

• BFS는 큐(Queue) 자료구조를 사용한다.
• 한 방향으로 쭉 파고드는 것이 아니라 수평적으로 넓게 탐색해 나간다.
• 방문한 노드는 다시 방문하지 않기 위해 방문 여부를 따로 관리한다.
• 최단 거리 문제에 강력한 성능을 보이며, DFS보다 경로의 길이를 예측하기 쉽다.

DFS와의 비교

BFS는 특히 JavaScript와 같은 언어에서 큐 구현이 단순하면서도 효율적일 경우 높은 성능을 보인다.
코딩 테스트에서 BFS는 최단 거리, 최소 이동 횟수, 레벨별 탐색 등의 키워드가 보이면 우선적으로 고려해야 할 알고리즘이다.

BFS 문제 예시

BFS를 실제로 적용해볼 수 있는 대표적인 예제로, 프로그래머스의 게임 맵 최단거리 문제가 있다.
이 문제는 캐릭터가 시작 지점에서 목표 지점까지 이동할 때, 가장 빠른 경로의 길이를 구하는 문제이다.

문제 설명

• maps는 2차원 배열이며, 각 값은 1 또는 0이다.
• 1은 이동 가능한 칸, 0은 벽을 의미한다.
• 캐릭터는 (0,0)에서 시작해서 (n-1, m-1)로 이동해야 한다.
• 상하좌우 네 방향으로만 이동이 가능하다.
• 최단 거리로 이동했을 때의 칸 수를 반환하고, 도달할 수 없으면 -1을 반환한다.

BFS 풀이 전략

• 1. **큐(Queue)**를 만들어 시작 위치를 넣는다.
• 2. 방문 여부를 기록할 2차원 배열 visited를 만든다.
• 3. 큐에서 좌표를 꺼내면서 상하좌우로 이동 가능한 위치를 확인한다.
• 4. 이동할 수 있고 아직 방문하지 않은 위치라면, 거리 +1을 큐에 넣는다.
• 5. 목표 지점 (n-1, m-1)에 도달하면 해당 거리를 바로 반환한다.

기본 BFS 구현 코드 (JavaScript)

function solution(maps) {
    const rows = maps.length;         
    const cols = maps[0].length;   
    const dy = [-1, 1, 0, 0];        
    const dx = [0, 0, -1, 1];   
    
    const visited = Array.from({ length: rows }, () => Array(cols).fill(0));
    const queue = [[0, 0, 1]];        // (y: 행, x: 열, dist: 거리)
    visited[0][0] = 1;
 
    while (queue.length) {
        const [y, x, dist] = queue.shift();
 
        for (let i = 0; i < 4; i++) {
            const ny = y + dy[i];    
            const nx = x + dx[i];    
 
            if (ny === rows - 1 && nx === cols - 1) {
                return dist + 1;
            }
 
            if (ny >= 0 && ny < rows && nx >= 0 && nx < cols && maps[ny][nx] === 1 && !visited[ny][nx]) {
                visited[ny][nx] = 1;
                queue.push([ny, nx, dist + 1]);
            }
        }
    }
 
    return -1;  
}
 

DFS(깊이 우선 탐색)란?

DFS(Depth-First Search)는 그래프나 트리 구조에서 한 방향으로 끝까지 파고드는 방식으로 탐색하는 알고리즘이다.
모든 경로를 탐색하거나, 특정 조건을 만족하는 조합이나 경우의 수를 찾는 데 자주 사용된다.

BFS가 너비를 우선적으로 탐색한다면, DFS는 깊이를 우선적으로 탐색한다.
보통 재귀 함수 또는 스택 자료구조를 이용하여 구현된다.

DFS 특징

• DFS는 재귀 호출 또는 스택(Stack) 을 사용한다.
• 한 방향으로 갈 수 있을 때까지 계속 내려가며 탐색한다.
• 주로 조합, 백트래킹, 완전 탐색 문제에 활용된다.
• 모든 경우의 수를 확인해야 할 때 매우 효과적인 방법이다.

DFS 문제 예시

DFS를 활용해볼 수 있는 대표적인 문제로, 프로그래머스의 타겟 넘버 문제가 있다.
이 문제는 주어진 숫자들에 + 또는 -를 붙여서 특정 target 값을 만들 수 있는 모든 경우의 수를 구하는 문제이다.

문제 설명

• 정수 배열 numbers와 목표 숫자 target이 주어진다.
• 각 숫자 앞에 + 또는 -를 붙여서 계산했을 때, 결과가 target이 되는 경우의 수를 반환한다.
• 모든 숫자는 정확히 한 번씩 사용해야 한다.

DFS 풀이 전략

• 1. 인덱스와 현재까지의 합을 인자로 받는 dfs 함수를 정의한다.
• 2. 종료 조건은 인덱스가 numbers.length와 같아질 때이다.
• 3. 종료 시점에서 현재 합이 target과 같으면 정답 카운트를 증가시킨다.
• 4. 현재 숫자에 +를 붙인 경우와 -를 붙인 경우 두 가지로 재귀 호출한다.

기본 DFS 구현 코드 (JavaScript)

function solution(numbers, target) {
    var answer = 0;
    const n = numbers.length;
    
    function dfs(length, sum){
        if(length===n){
            if(sum===target)    answer++;
            return;
        }
        
        dfs(length+1, sum+numbers[length]);
        dfs(length+1, sum-numbers[length]);
    }
    
    dfs(0, 0);
    
    return answer;
}

결론

BFS와 DFS는 그래프 탐색의 두 가지 주요 방법으로, 각각의 특징과 장단점이 있다.
BFS는 최단 경로 문제에 강력하며, DFS는 모든 경우의 수를 탐색할 때 유용하다.
이 두 알고리즘을 잘 이해하고 활용하면, 다양한 문제를 효과적으로 해결할 수 있다.