[ZBF] 6월 18일 코딩 테스트 : DFS / BFS

이 글은 네이버 블로그에 2024년 6월 18일에 올렸던 것을 그대로 옮겨온 것입니다.

깊이 / 너비 우선 탐색 ( DFS / BFS )

알고리즘 문제를 풀다 보면 그래프 탐색 알고리즘인 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)를 자주 접하게 됩니다. 이번 글에서는 DFS와 BFS의 개념, 구현 방법, 그리고 차이점에 대해 정리해 보겠습니다.

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

개념

DFS는 그래프의 모든 정점을 방문하는 탐색 알고리즘입니다. 시작 정점에서 출발하여 한 경로를 따라 갈 수 있는 곳까지 깊이 탐색한 후, 더 이상 갈 수 없으면 이전 정점으로 돌아가 다른 경로를 탐색합니다. 즉, DFS는 가능한 깊이 있는 곳까지 탐색을 진행합니다.

특징

• 스택을 사용: DFS는 주로 재귀 호출이나 명시적인 스택 자료구조를 사용하여 구현합니다.
• 모든 경로를 탐색: DFS는 모든 경로를 탐색하기 때문에 경로의 깊이를 우선으로 탐색합니다.
• 시간 복잡도: O(V + E) (V는 정점의 수, E는 간선의 수)

// 깊이 우선 탐색 구현 (재귀)
function dfs(graph, startNode) {
    const visited = new Set();
    
    function dfsRecursive(node) {
        if (visited.has(node)) return;
        
        console.log(node); // 방문 노드 출력
        visited.add(node);
        
        graph[node].forEach(neighbor => {
            dfsRecursive(neighbor);
        });
    }
    
    dfsRecursive(startNode);
}

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

dfs(graph, 0);

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

개념

BFS는 시작 정점에서 출발하여 가까운 정점부터 차례대로 탐색하는 알고리즘입니다. BFS는 현재 정점에서 인접한 정점을 먼저 탐색하고, 그 다음 인접한 정점을 탐색하는 방식으로 진행됩니다. BFS는 주로 최단 경로를 찾거나, 레벨 단위로 그래프를 탐색할 때 유용합니다.

특징

• 큐를 사용: BFS는 큐 자료구조를 사용하여 구현합니다.
• 최단 경로 탐색: BFS는 최단 경로를 보장합니다.
• 시간 복잡도: O(V + E) (V는 정점의 수, E는 간선의 수)

// 너비 우선 탐색 구현
function bfs(graph, startNode) {
    const visited = new Set();
    const queue = [startNode];
    
    visited.add(startNode);
    
    while (queue.length > 0) {
        const node = queue.shift();
        console.log(node); // 방문 노드 출력
        
        graph[node].forEach(neighbor => {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        });
    }
}

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

bfs(graph, 0);

DFS와 BFS의 차이점

DFS와 BFS는 그래프 탐색을 위한 중요한 알고리즘입니다. 각각의 특성과 사용 목적을 이해하고 적절하게 활용하는 것이 중요합니다. DFS는 깊이 있는 탐색이 필요할 때, BFS는 최단 경로 탐색이 필요할 때 주로 사용됩니다.

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)의 시간 복잡도는 둘 다 그래프의 정점(Vertex)와 간선(Edge)의 개수에 비례합니다.

시간 복잡도

깊이 우선 탐색(DFS)

DFS의 시간 복잡도는 그래프의 모든 정점과 간선을 한 번씩 방문하기 때문에 다음과 같습니다.

• 시간 복잡도: O(V + E)
  • V는 정점(Vertex)의 수
  • E는 간선(Edge)의 수

너비 우선 탐색(BFS)

BFS의 시간 복잡도도 그래프의 모든 정점과 간선을 한 번씩 방문하기 때문에 다음과 같습니다.

• 시간 복잡도: O(V + E)
  • V는 정점(Vertex)의 수
  • E는 간선(Edge)의 수

설명

• 정점(Vertex)의 수: 그래프에 존재하는 모든 노드의 수입니다. 탐색 과정에서 각 정점을 한 번씩 방문하기 때문에 시간 복잡도에 영향을 미칩니다.
• 간선(Edge)의 수: 각 정점에서 연결된 모든 간선을 한 번씩 검사합니다. 간선을 검사하는 과정도 시간 복잡도에 포함됩니다.

따라서 DFS와 BFS는 모두 그래프의 크기와 구조에 따라 탐색하는데 필요한 시간은 O(V + E)입니다.

https://school.programmers.co.kr/learn/courses/30/parts/12421

• 프로그래머스 스쿨 - 온라인 IT 특화 교육 전문 플랫폼 — 프로그래머스 스쿨은 IT 분야 교육 전반의 과정을 제공하는 온라인 교육 플랫폼입니다. 프로그래밍, 데이터, 인공지능 등의 학습부터 코딩 테스트, 과제 테스트 연습까지, 프로그래머스 스쿨과 함께 성장해 보세요!