DFS & BFS 탐색 문제 개념 정리(개념, 코드, 시간/공간복잡도 비교)

🔎 1️⃣ DFS & BFS 문제에서 묻는 것

그래프 탐색 문제에서 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)를 구현할 수 있는지를 확인합니다.

✅ 주요 개념

• DFS(Depth-First Search, 깊이 우선 탐색)
  • 그래프에서 한 경로를 깊게 탐색하다가 막히면 다시 되돌아가며 탐색하는 방식
  • 재귀(Recursive) 또는 스택(Stack)으로 구현
• BFS(Breadth-First Search, 너비 우선 탐색)
  • 시작점에서 가까운 노드부터 탐색하는 방식
  • 큐(Queue)를 활용하여 구현

✅ 이 문제에서 확인하려는 핵심 내용

1. 그래프 탐색 알고리즘을 이해하고 있는가?
2. DFS와 BFS를 직접 구현할 수 있는가?
3. 스택(Stack), 큐(Queue) 자료구조를 활용할 수 있는가?
4. 시간복잡도와 공간복잡도를 고려하여 효율적으로 탐색할 수 있는가?

---

🔎 2️⃣ DFS (깊이 우선 탐색) 개념 및 코드

DFS는 한 노드에서 최대한 깊숙이 들어간 후 더 이상 갈 곳이 없으면 되돌아오는 방식입니다.

📌 DFS 탐색 순서

1️⃣ 현재 노드를 방문(출력)
2️⃣ 방문하지 않은 인접 노드로 이동
3️⃣ 더 이상 방문할 곳이 없으면 백트래킹(되돌아가기)

📌 DFS 코드 (재귀 방식)

function dfs(graph, node, visited = new Set()) {
    if (visited.has(node)) return; // 이미 방문한 노드는 탐색하지 않음

    console.log(node); // 방문한 노드 출력
    visited.add(node); // 방문 처리

    for (let neighbor of graph[node]) {
        dfs(graph, neighbor, visited);
    }
}

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

dfs(graph, 1); // 1 → 2 → 4 → 5 → 3 → 6​

📌 DFS 코드 (스택 방식)

function dfsStack(graph, start) {
    let stack = [start];
    let visited = new Set();

    while (stack.length > 0) {
        let node = stack.pop(); // 스택에서 하나 꺼냄
        if (!visited.has(node)) {
            console.log(node); // 방문한 노드 출력
            visited.add(node);

            // 방문할 노드를 스택에 추가 (역순으로 넣어야 순서대로 탐색됨)
            for (let neighbor of graph[node].reverse()) {
                stack.push(neighbor);
            }
        }
    }
}

dfsStack(graph, 1);​

📌 DFS의 시간복잡도 & 공간복잡도

• 시간복잡도: O(V + E) (V: 정점 개수, E: 간선 개수)
• 공간복잡도: O(V) (노드 방문 여부 저장)
• 재귀 방식의 경우: O(V) (재귀 호출을 위한 스택 공간 추가)

---

🔎 3️⃣ BFS (너비 우선 탐색) 개념 및 코드

BFS는 한 노드에서 가까운 노드부터 탐색하는 방식입니다.

📌 BFS 탐색 순서

1️⃣ 현재 노드를 방문(출력)
2️⃣ 방문하지 않은 모든 인접 노드를 큐에 추가
3️⃣ 큐에서 하나씩 꺼내며 탐색

📌 BFS 코드 (큐 방식)

function bfs(graph, start) {
    let queue = [start];
    let visited = new Set();

    while (queue.length > 0) {
        let node = queue.shift(); // 큐에서 하나 꺼냄
        if (!visited.has(node)) {
            console.log(node); // 방문한 노드 출력
            visited.add(node);

            // 방문할 노드를 큐에 추가
            for (let neighbor of graph[node]) {
                queue.push(neighbor);
            }
        }
    }
}

bfs(graph, 1); // 1 → 2 → 3 → 4 → 5 → 6

 

📌 BFS의 시간복잡도 & 공간복잡도

• 시간복잡도: O(V + E) (V: 정점 개수, E: 간선 개수)
• 공간복잡도: O(V) (큐에 저장하는 노드 개수)

---

🔎 4️⃣ DFS vs BFS 비교

구분	DFS(깊이 우선 탐색)	BFS(너비 우선 탐색)
구현 방식	스택(Stack) / 재귀(Recursive)	큐(Queue) 사용
방문 순서	한 경로를 끝까지 탐색 후 백트래킹	가까운 노드부터 탐색
공간복잡도	O(V) (스택 또는 재귀 호출)	O(V) (큐 저장 공간)
시간복잡도	O(V + E)	O(V + E)
활용 예시	백트래킹, 퍼즐 풀이, 최단 경로 문제 X	최단 경로 탐색 (미로, 네트워크)

✅ DFS가 유리한 경우

• 그래프가 깊고, 가지치기를 활용할 수 있는 경우
• 백트래킹 문제(예: 미로 탈출, 퍼즐 풀이)

✅ BFS가 유리한 경우

• 최단 경로를 찾아야 하는 경우 (예: 미로 최단 경로)
• 트리에서 특정 노드까지의 거리 계산

---

🔎 5️⃣ DFS/BFS를 효율적으로 사용하려면?

✅ 그래프 표현 방식

1. 인접 리스트(Adjacency List)

• 노드 개수가 많을 때 메모리 효율적
• 예제:

const graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6],
    4: [],
    5: [],
    6: []
};​

 

 

2. 인접 행렬(Adjacency Matrix)

• 노드 개수가 적고 간선이 많을 때 유리
• 예제:

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

 

✅ 재귀 vs 반복문

• DFS는 재귀로 구현하면 간단하지만, 노드 개수가 많을 경우 스택 오버플로우 위험 → 반복문(스택) 사용 권장
• BFS는 큐를 활용하는 것이 일반적

✅ 그래프 유형별 접근 방법

• 트리 탐색 → DFS, BFS 둘 다 가능
• 최단 거리 문제 → BFS 사용
• 경로 탐색 및 조합 문제 → DFS 사용

---

🔎 6️⃣ 정리

📌 DFS는 한 경로를 깊게 탐색하고, BFS는 가까운 곳부터 탐색한다.
📌 BFS는 최단 경로 탐색에 유리하고, DFS는 백트래킹과 탐색 문제에 적합하다.
📌 코딩 테스트에서는 보통 인접 리스트를 사용하여 구현하며, 스택/큐 활용 능력을 평가한다.