DFS & BFS

그래프 탐색 알고리즘이란 어떤 노드(정점)에서 출발해서 연결된 노드를 빠짐없이 방문하는 방법에 대한 규칙입니다. 오늘은 그 중에서도 가장 기본이 되는 두가지 탐색 방식, DFS와 BFS를 알아보겠습니다.

 

 

 

DFS와 BFS란?

DFS(Depth-First Search, 깊이 우선 탐색) 는 한 방향으로 갈 수 있는데까지 끝까지 들어갔다가, 더 갈 곳이 없으면 되돌아와서 다른 방향을 탐색하는 방식입니다.

 

BFS(Breadth-First Search, 너비 우선 탐색) 는 출발 노드에서 가까운 노드부터 먼저 전부 방문하고, 그 다음 거리에 있는 노드들을 방문하는 방식입니다. 

 

쉽게 말하면, DFS는 "일단 끝까지 파고들기", BFS는 "주변부터 차근차근 퍼져나가기"라고 볼 수 있습니다.

 

 

 

핵심 개념

① DFS ㅡ 스택(Stack) 또는 재귀(Recursion)를 사용

DFS는 방문한 경로를 쌓아두고 막히면 되돌아가는 방식으로 동작합니다. 이 "쌓아두고 되돌아가는" 구조가 스택과 똑같기 때문에, 재귀 함수로 구현하면 콜스택이 이 역할을 자동으로 해줍니다.

콜스택(Call Stack)이란? 함수가 호출될 때마다 그 함수 정보를 쌓아두는 공간입니다. 재귀로 dfs()를 호출하면 호출할 때마다 스택에 쌓이고, 함수가 끝나면 하나씩 꺼내지면서 자동으로 이전 위치로 돌아옵니다. DFS의 "되돌아가기"가 바로 이 원리입니다. 

 

② BFS ㅡ 큐(Queue)를 사용

BFS는 방문할 노드를 줄 세워두고 앞에서부터 하나씩 꺼내 처리하는 방식입니다. 먼저 들어온 것이 먼저 나가는 큐의 구조가 "가까운 것부터 방문한다"는 BFS의 성질과 맞아떨어집니다.

 

③ 방문 처리가 필수

둘 다 한 번 방문한 노드는 다시 방문하지 않도록 체크해둬야 합니다. 체크하지 않으면 무한 루프에 빠질 수 있습니다.

 

 

 

그래서 이걸 왜 배우는 걸까요?

미로를 탈출하는 게임을 생각해봅시다. 출구를 찾기 위해 두 가지 전략을 쓸 수 있습니다. 하나는 한 방향을 정해서 막힐 때까지 쭉 가다가 막히면 되돌아오는 것이고, 다른 하나는 현재 위치에서 갈 수 있는 길을 모두 한 칸씩 탐색하면서 넓게 퍼지는 것입니다.

 

첫번째가 DFS, 두번째가 BFS입니다. 미로만이 아니라 SNS 친구 추천(몇 촌 관계인지), 네비게이션의 경로 탐색, 게임의 AI 로직까지 이 두 알고리즘이 그 뼈대가 됩니다.

 

 

 

실습 ㅡ 동작 과정 따라가기

아래 그래프에서 A를 시작으로 탐색하는 과정을 단계별로 보겠습니다. 연결 관계는 다음과 같습니다.

A — B — D
|                |
C — E      F

 

DFS 과정

1. A 방문 → 연결된 B, C  중 B 선택
2. B 방문 → 연결된 D 선택
3. D 방문 → 연결된 F 선택
4. F 방문 → 더 갈 곳 없음 → 되돌아감
5. B로 돌아와도 더 갈 곳 없음 → A로
6. A에서 C 선택 → C 방문, E 방문

방문 순서: A → B → D → F → C → E

 

 

BFS 과정

1. A 방문, 큐에 B, C 추가
2. B 꺼냄 → 방문, 큐에 D 추가
3. C 꺼냄 → 방문, 큐에 E 추가
4. D 꺼냄 → 방문, 큐에 F 추가
5. E 꺼냄 → 방문
6. F 꺼냄 → 방문

방문 순서: A → B → C → D → E → F

 

 

 

코드로 보기

// 그래프 (인접 리스트 방식)
const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'E'],
  D: ['B', 'F'],
  E: ['C'],
  F: ['D']
};

// DFS - 재귀로 구현
function dfs(graph, node, visited = new Set()) {
	visited.add(node);
    console.log(node);
    
    for (const neighbor of graph[node]) {
    	if (!visited.has(neighbor)) {
        	dfs(graph, neighbor, visited);  // 재귀로 더 깊이
        }
    }
}

// BFS - 큐로 구현
function bfs(graph, start) {
	const visited = new Set();
    const queue = [start];  // 큐에 시작 노드 추가
    visited.add(start);
    
    while (queue.length > 0) {
    	const node = queue.shift();  // 앞에서 꺼냄
        console.log(node);
        
        for (const neighbor of graph[node]) {
        	if (!visited.has(neighbor)) {
            	visited.add(neighbor);
                queue.push(neighbor);  // 뒤에서 추가
            }
        }
    }
}

dfs(graph, 'A');  // A B D F C E
bfs(graph, 'A');  // A B C D E F

 

 

 

참고 ㅡ DFS와 BFS 비교

같은 그래프라도 무엇을 구해야 하느냐에 따라 적합한 알고리즘이 달라집니다. 문제를 보고 "이건 깊이 우선이 맞나, 너비 우선이 맞나"를 판단하는 것이 핵심입니다.

 

항목	DFS	BFS
사용 자료구조	스택 / 재귀	큐
탐색 방향	깊이 우선 (끝까지)	너비 우선 (가까운 순서)
최단 경로 보장	X	✓ (가중치 없는 그래프)
적합한 상황	경로 존재 여부, 사이클 탐지	최단 거리, 레벨별 탐색
메모리 사용	상대적으로 적음	노드 수에 비례해 많아질 수 있음

 

기중치 없는 그래프란? 노드 사이의 이동 비용이 모두 동일한 그래프입니다. 예를 들어 A → B → C와 A → D → C가 있을 때, 모든 이동이 똑같이 1칸이라면 BFS는 출발지에서 가까운 순서대로 탐색하기 때문에 처음 도착한 경로가 곧 최단 경로가 됩니다. 반면 경로마다 거리나 비용이 다르다면 (가중치가 있다면) BFS만으로는 최단 경로를 보장할 수 없고, 다익스트라 같은 별도 알고리즘이 필요합니다.

 

 

 

마치며

DFS와 BFS, 두 알고리즘을 모두 이해하고 나면 자연스럽게 이런 질문이 생깁니다. "이 문제는 DFS로 풀어야 할까, BFS로 풀어야 할까?" 바로 그 판단을 할 수 있게 되는 것이 이번 학습 목표입니다.

 

알고리즘을 외우는 것보다, 어떤 상황에서 어떤 탐색 방식이 자연스러운지 느낌을 갖는 것이 중요합니다. 궁금한 점이 있다면 댓글 남겨주세요!