[알고리즘] DFS, BFS

DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프나 트리 탐색에서 사용하는 대표적인 탐색 알고리즘이다. 두 알고리즘 모두 특정 노드를 방문하고, 그 노드와 연결된 다른 노드들을 탐색하는 방식으로 동작한다. DFS는 깊이를 우선으로 탐색하고, BFS는 너비를 우선으로 탐색한다.

 

1. DFS (Depth-First Search, 깊이 우선 탐색)

DFS는 탐색할 때 가능한 한 깊게 들어가는 방식으로 탐색한다. 즉, 한 경로를 따라 끝까지 가고, 더 이상 갈 곳이 없으면 다시 돌아와 다른 경로를 탐색한다. 이 방식은 재귀나 스택을 사용해 구현할 수 있다.

 

DFS 예시: 그래프 탐색

function dfs(graph, start, visited = new Set()) {
    // 현재 노드 방문 처리
    visited.add(start);
    console.log(start);

    // 현재 노드와 연결된 노드들을 재귀적으로 방문
    for (let neighbor of graph[start]) {
        if (!visited.has(neighbor)) {
            dfs(graph, neighbor, visited);
        }
    }
}
// 그래프 표현 (인접 리스트)
const graph = {
    1: [2, 3],
    2: [4],
    3: [5],
    4: [],
    5: []
}

dfs(graph, 1);  // 출력: 1 2 4 3 5

 

DFS의 시간 복잡도

• 시간 복잡도: O(V + E) (V는 노드 수, E는 간선 수)
• 그래프의 모든 노드를 방문하고 모든 간선을 처리해야 하기 때문에, 위와 같은 복잡도를 가진다.

---

 

2. BFS (Breadth-First Search, 너비 우선 탐색)

BFS는 탐색할 때 가까운 노드부터 차례대로 방문한다. 즉, 특정 노드에서 연결된 모든 노드를 먼저 탐색한 후, 그 다음 깊이의 노드들을 탐색한다. 이 방식은 큐(Queue) 자료 구조를 사용해 구현한다.

 

BFS 예시: 최단 경로 탐색

function bfs(graph, start) {
    const queue = [start]; // 탐색할 노드를 저장할 큐
    const visited = new Set(); // 방문한 노드를 저장할 집합
    visited.add(start);

    while (queue.length > 0) {
        const node = queue.shift(); // 탐색할 노드를 큐에서 꺼냄
        console.log(node);

        for (let neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
}

// 그래프 표현 (인접 리스트)
const graph = {
    1: [2, 3],
    2: [4],
    3: [5],
    4: [],
    5: []
};

bfs(graph, 1);  // 출력: 1 2 3 4 5

 

BFS의 시간 복잡도

• 시간 복잡도: O(V + E) (V는 노드 수, E는 간선 수)
• 모든 노드와 모든 간선을 한 번씩 방문하기 때문에 DFS와 마찬가지로 같은 복잡도를 가진다.

---

 

DFS와 BFS의 차이

• 탐색 방식: DFS는 깊이 우선으로 탐색하며, BFS는 너비 우선으로 탐색한다.
• 구현 방식: DFS는 재귀나 스택을 사용하고, BFS는 큐를 사용해 구현한다.
• 사용 사례:
  • DFS는 경로 탐색(예: 미로 찾기)나 백트래킹이 필요한 문제에 적합하다.
  • BFS는 그래프에서 최단 경로를 찾는 문제에 적합하다.

---

 

예시 문제

 

1. 미로 찾기

문제: N x M 크기의 미로가 주어질 때, 출발점에서 도착점까지 최단 경로를 찾으세요. 벽은 통과할 수 없으며, 상하좌우로만 이동할 수 있습니다.

 

// BFS
function shortestPath(maze, start, end) {
    const directions = [[0, 1], [1, 0], [0, -1], [1, 0]];
    const queue = [[start, 0]]; // [현재위치, 이동거리]
    const visited = new Set();
    visited.add(start.toString());

    while (queue.length > 0) {
        const [[x, y], distance] = queue.shift();

        if (x === end[0] && y === end[1]) return distance;

        for (let [dx, dy] of directions) {
            const newX = x + dx;
            const newY = y + dy;

            if (newX >= 0 && newY >= 0 &&
                newX < maze.length && newY < maze[0].length &&
                maze[newX][newY] === 0 && !visited.has([newX, newY].toString())
            ) {
                visited.add([newX, newY].toString());
                queue.push([[newX, newY], distance + 1]);
            }
        }
    }

    return -1; // 도착할 수 없는 경우
}

const maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
];

console.log(shortestPath(maze, [0, 0], [4, 4]));  // 출력: 8 (최단 경로 거리)

 

---

2. 섬 개수 세기

문제: 2차원 배열에서 육지를 1, 바다를 0으로 나타내는 섬의 지도에서, 섬(연결된 1의 집합)의 개수를 구하세요.

 

// DFS
function numIslands(grid) {
    let count = 0;

    function dfs(grid, x, y) {
        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] === '0') {
            return;
        }

        grid[x][y] = '0'; // 방문한 곳은 0 처리
        dfs(grid, x + 1, y);
        dfs(grid, x - 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x, y - 1);
    }

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1') {
                count++;
                dfs(grid, i, j);
            }
        }
    }

    return count;
}

const grid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
];

console.log(numIslands(grid));  // 출력: 3 (3개의 섬)