🎧

 
 
애증의 DFS와 BFS.. 이해안 되는 줄 알았는데 됐어요
 
를 기념하며 DFS와 BFS에 대해 설명해보려고 합니다.

저는 코드를 보기 보다 먼저 머리로 이해하는 것이 나중을 위해서 좋더라고요

코드를 외우기 보다는 원리를 이해하고 접근하는 것이 응용 문제 혹은 실제 문제 상황을 대비하기에 적합한 것 같습니다

그럼 시작!

 
DFS는 약자입니다.

Depth-First Search의 약자입니다.

'깊이 우선 탐색'이라고 하죠

DFS는 한 경로를 끝까지 파고들어서 탐색한 다음, 더 이상 갈 곳이 없으면 뒤로 돌아와서 다른 경로를 탐색하는 방식입니다.
'깊이'를 우선해서 탐색한다는 의미입니다
 
 

🛠 동작 과정

1. 시작 노드 방문
   • 출발 지점에서 탐색을 시작합니다.
   • 이 노드를 방문 처리(visited 표시)합니다.
2. 연결된 노드 중 방문하지 않은 노드로 이동
   • 현재 노드와 연결된 노드들 중에서 방문하지 않은 노드를 선택합니다.
   • 선택된 노드로 이동해서 다시 같은 과정을 반복합니다.
3. 더 이상 갈 곳이 없으면 뒤로(backtrack)
   • 현재 노드에서 더 이상 방문할 수 있는 새로운 노드가 없다면,
     이전 단계(바로 전 노드)로 돌아갑니다.
   • 그리고 다른 방문하지 않은 경로가 있는지 확인합니다.
4. 모든 노드 방문할 때까지 반복
   • 모든 경로를 탐색하면 종료합니다.

DFS의 구현 방식

DFS는 크게 두 가지 방식으로 구현됩니다.
 
 

1. 재귀 방식

function dfs(node) {
    visited.add(node);
    for (let next of graph[node]) {
        if (!visited.has(next)) {
            dfs(next);
        }
    }
}

 
이 방식은 코드가 간결하지만, 너무 깊은 그래프에서는 재귀 호출이 많아져서 스택 오버플로우 위험이 있음.
 
 

2. 스택 방식

function dfsStack(start) {
    let stack = [start];
    while (stack.length) {
        let node = stack.pop();
        if (!visited.has(node)) {
            visited.add(node);
            stack.push(...graph[node]);
        }
    }
}

 
재귀 대신 명시적으로 스택 자료구조를 사용.
 

DFS 특징?

• 깊이 우선 → 한 경로를 끝까지 탐색 후 돌아옴.
• 재귀나 스택을 이용해 구현.
• 모든 경우의 수 탐색이나 백트래킹에서 자주 쓰임.
• 최단 거리 보장 X → BFS와 달리, 먼저 찾은 해답이 최단 경로가 아닐 수 있음.

쉽게 생각하면,,

한 경로를 끝까지 따라가며 탐색한 뒤, 되돌아와 다른 경로를 탐색하는 방식
이라고 이해하시면 됩니다

👀DFS의 전형적 함수 예시

function dfs(node, depth) {
    // node: 현재 탐색 중인 노드(또는 시작점)
    // depth: 현재까지 내려온 깊이(또는 경로 길이)
}

1. node
• 지금 방문하고 있는 위치나 값.
• 그래프 문제라면 정점 번호,
• 문자열 변환 문제라면 현재 단어,
• 트리 탐색이라면 현재 노드 객체.

2. depth / step / count (문제에 따라 선택적으로 사용)
• 현재까지 이동한 단계 수, 재귀 깊이, 혹은 변환 횟수.
• 최소 경로, 최소 변환 횟수 같은 문제에서 중요.

3. visited (보통 전역 또는 외부 변수로 전달)
• 이미 방문한 노드를 기록하는 배열/Set/객체.
• 같은 노드를 중복 탐색하지 않게 함.

4. target (선택적)
• 어떤 조건을 만족하는지 체크할 대상 값.
• 예: 찾고 싶은 숫자, 단어, 혹은 도착점 노드.

✔️DFS에서 핵심 파라미터 조합은 보통
dfs(현재 위치, 현재 깊이, 방문 기록, 목표 값)
이렇게 구성돼요.

BFS는 그럼 뭘까요

BFS(너비 우선 탐색)는 가까운 곳부터 차례대로 탐색하는 방식입니다

좀 더 쉽게 말하면,
🚶 “출발점에서 한 걸음씩 주변을 전부 살펴본 다음, 그 다음 거리로 이동하는 탐색”
같은 개념이죠.

BFS의 특징은

큐(Queue) 자료구조 사용 → 먼저 들어온 노드부터 처리(FIFO).

최단 거리 탐색에 유리 → 가중치가 없는(이동마다 연산이 드는) 그래프에서 가장 짧은 경로 보장.

한 번 방문한 노드는 다시 방문하지 않도록 visited 체크 필수.

간단 예시 코드

function bfs(start) {
    const queue = [start];
    const visited = new Set([start]);

    while (queue.length > 0) {
        const node = queue.shift();
        // node 처리
        for (let next of node.인접노드들) {
            if (!visited.has(next)) {
                visited.add(next);
                queue.push(next);
            }
        }
    }
}

1. start / node
• 탐색 시작점 또는 현재 탐색 중인 노드.
• 그래프/트리 문제면 정점 번호나 객체, 문자열 변환 문제면 현재 단어.

2. depth / level / count
• 현재까지 이동한 거리(단계 수).
• 최단 경로 문제에서 매우 중요.
• BFS는 가까운 곳부터 탐색하니까, 이 값이 그대로 최단 거리임.

3. visited
• 이미 방문한 노드를 저장하는 구조(Set, 배열, 객체).
• 중복 방문 방지 → 무한 루프 예방.
• BFS에서는 방문 체크를 큐에 넣을 때 하는 게 보통.

4. queue
• 다음에 탐색할 노드들을 담는 자료구조(FIFO).
• 각 요소는 보통 [node, depth] 같이 현재 위치와 단계 수를 함께 저장.


5. target (선택적)
• 찾으려는 값이나 조건.
• BFS 도중 조건을 만족하면 즉시 탐색 종료 가능.

위 파라미터 사용 예시

function bfs(start, target) {
    const queue = [[start, 0]]; // [현재 노드, 단계 수]
    const visited = new Set([start]);

    while (queue.length) {
        const [node, depth] = queue.shift();
        if (node === target) return depth;

        for (let next of node.인접노드들) {
            if (!visited.has(next)) {
                visited.add(next);
                queue.push([next, depth + 1]);
            }
        }
    }
    return -1; // 찾지 못한 경우
}

실무에서는 어떻게 활용할까?

DFS

DOM 탐색

HTML 트리를 깊이 우선으로 탐색해 특정 노드 찾기. 예: 이벤트 위임 시 부모/자식 관계 검색

컴포넌트 구조 분석

React/Vue 컴포넌트 트리에서 props/state 전파 경로 분석

중첩 데이터 처리

계층형 데이터(폴더 구조, 메뉴, 댓글 스레드 등)를 깊게 내려가며 처리

백트래킹 기반 기능

예: 폼 입력 시 가능한 모든 조합 탐색, 퍼즐형 기능(스도쿠, 경로 찾기)

BFS

최단 경로 탐색

예: 지도 서비스(최단 경로), UI 내 요소 간 최소 이동 횟수 계산

근접 탐색 기능

예: 추천 시스템에서 가까운 관련 항목부터 찾기

상태 전파

실시간 채팅방, 알림 시스템에서 이벤트를 가까운 곳부터 전달

트리/그래프에서 레벨별 데이터 처리

예: UI 메뉴의 깊이별 표시, 계층형 데이터의 단계별 로딩


이렇게 DFS와 BFS에 대해 알아보았습니다!
복습 반복만이 살 길!