태야

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

<내 코드>

from collections import deque


def bfs(x, y):
    direction = [(1, 0), (-1, 0), (0, 1), (0, -1),
                 (1, 1), (1, -1), (-1, 1), (-1, -1)]

    queue = deque() #탐색을 하려는 좌표를 담는다.
    queue.append((x, y))

    maps[x][y] = 0

    while queue:
        now = queue.popleft()

        for i in range(8): #상하좌우 대각선까지 탐색
            nx = now[0] + direction[i][0]
            ny = now[1] + direction[i][1]

            if(0 <= nx < h) and (0 <= ny < w):
                if maps[nx][ny] == 1:
                    maps[nx][ny] = 0
                    queue.append((nx, ny))


while True:

    w, h = map(int, input().split())
    maps = []
    cnt = 0

    if w == 0 and h == 0:
        break

    for _ in range(h):
        tmp = list(map(int, input().split()))
        maps.append(tmp)

    for i in range(h):
        for j in range(w):
            if maps[i][j] != 0:
                cnt += 1
                bfs(i, j)

    print(cnt)

1. w, h, 지도를 입력받는다.

2. 매 입력마다 BFS 탐색을 마치면 cnt를 +1 해준다.

3. BFS를 상하좌우 그리고 대각선까지 여덟 방향을 다 탐색한다.

4. 탐색 중 지도에서 1인 값을 0으로 바꾸고 큐에 좌표를 넣고 탐색을 반복한다.

<내 코드>

import sys
sys.setrecursionlimit(10000)


def dfs(v):

    done[v] = v

    for i in gragh[v]:
        if (i != 0) and (i not in done):
            dfs(i)


vertex, edge = map(int, input().split())
gragh = [[0]*(vertex + 1) for _ in range(vertex + 1)]
done = [0]*(vertex + 1)
cnt = 0

for _ in range(edge):
    x, y = map(int, input().split())
    gragh[x][y] = y
    gragh[y][x] = x

for w in range(1, vertex+1):
    if w not in done:
        dfs(w)
        cnt += 1

print(cnt)

처음에 런타임 에러가 계속 나서 뭐가 문제인지 몰랐다.. 검색 결과 python은 재귀 제한이 걸려있기 때문에 재귀 허용치가 넘어가면 런타임 에러를 일으킨다. 때문에 sys.setrecursionlimit(10000)처럼 작성해야 한다는 것을 알게 됐다.

sys.setrecursionlimit() 메서드는 Python 인터프리터 스택의 최대 깊이를 필요한 제한으로 설정하는 데 사용된다. 이 제한은 모든 프로그램이 무한 재귀에 들어가는 것을 방지한다. 제한이 너무 높으면 충돌이 발생해 주의가 필요하다.