태야

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개의 섬)

 이분 탐색 알고리즘 - 파이썬

이분 탐색은 값을 비교할 때마다 찾는 값이 있을 범위를 절반씩 좁히면서 탐색하는 효율적인 알고리즘이다. 이분 탐색에서 중요한 것은 '이미 정렬된 데이터'에서 값을 비교하면 찾는다는 것이다. 따라서 순차 탐색처럼 처음부터 하나씩 하는 것이 아니라 정렬된 데이터에서 기준점을 잡고 반으로 줄여나가며 찾는 것이기에 훨씬 효율적이고 빠른 알고리즘이다.

이분 탐색은 실생활에서 '책'을 떠올리면 쉽게 이해할 수 있다. 우리는 책을 이용해 원하는 것을 찾을 때 첫 페이지부터 찾는 것이 아니라, 중간쯤 쪽수를 찾아 펼친 다음 범위를 좁혀나가며 계속 찾아나간다. 원하는 페이지가 펼친 페이지보다 뒤에 있다면 앞쪽은 찾을 필요 없이 바로 뒤쪽부터 찾게 된다.

예제

def binary_search(a, x):
    start = 0
    end = len(a)-1

    while start <= end:
        mid = (start + end) // 2
        if(x == a[mid]): 	# 원하는 값 발견!
            return mid 
        elif (x > a[mid]): 	# 찾는 값이 더 크면, 오른쪽으로 범위를 좁혀 탐색
            start = mid + 1
        else:			# 찾는 값이 더 작으면, 왼쪽으로 범위를 좁혀 탐색
            end = mid - 1
            
    return -1			# 찾지 못했을 때

a = [1, 4, 9, 25, 36, 49] # 정렬된 자료
print(binary_search(a, 36)) # 5
print(binary_search(a, 12)) # -1