BFS·DFS 알고리즘 직관적 이해와 코딩테스트 실전 활용법

그래프 탐색은 코딩테스트에서 가장 자주 만나는 주제 중 하나다. 면접관들은 BFS와 DFS를 얼마나 잘 이해하는지로 지원자의 기초 실력을 판단하는 경향이 있다. 단순히 코드를 외우는 수준으로는 문제를 풀 때 어떤 방식을 선택해야 할지 판단하기 어렵다. 이번 글에서는 두 알고리즘이 왜 다르게 동작하는지, 그리고 어떤 상황에서 어떤 것을 쓸지에 대해 정리해보겠다.

그래프 탐색이 필요한 이유

먼저 왜 탐색 알고리즘이 필요한지부터 생각해보자. 실제 문제에서는 '모든 노드를 한 번씩 방문해야 하는 상황'이 자주 나타난다. 미로 찾기, 연결된 요소 찾기, 특정 경로 존재 여부 판단 등이 그 예다. 이런 상황에서 체계적으로 노드를 방문하는 방법이 필요하다. 여기서 등장하는 게 DFS와 BFS다.

DFS: 깊이 우선 탐색이란

DFS는 Depth-First Search의 약자로, 한국어로 깊이 우선 탐색이라고 부른다. 이름 그대로 깊이를 우선으로 한다는 뜻이다. 한 방향으로 막힐 때까지 계속 파고들어가는 방식이라고 생각하면 이해하기 쉽다.

 

예를 들어, 미로를 풀 때 한 경로를 끝까지 따라가본다고 생각해보자. 막다른 골목에 도달하면 돌아나와 다른 경로를 시도한다. 이런 식으로 계속 진행하는 방식이 DFS다. 이를 구현할 때는 스택(Stack) 자료구조를 사용하거나 재귀 호출을 이용한다. 재귀는 함수 호출 스택을 내부적으로 사용하므로 별도의 스택을 만들 필요가 없다.

DFS(노드):
    현재 노드 방문 표시
    현재 노드의 인접 노드 중에서:
        방문하지 않은 노드가 있으면:
            그 노드에서 DFS 반복

 

재귀로 구현하면 코드가 직관적이다. 동작 과정을 따라가보자. A라는 노드에서 시작했다고 하면, A의 첫 번째 이웃 B로 간다. B에서 또 더 깊이 들어가 가능한 모든 경로를 탐색한다. B에서 더 이상 갈 곳이 없으면 돌아와 A의 다음 이웃으로 간다. 이런 방식으로 계속 진행된다.

BFS DFS 그래프 탐색 경로 비교

BFS: 너비 우선 탐색이란

BFS는 Breadth-First Search로, 너비 우선 탐색이다. 깊이 우선과 정반대 방식이다. 현재 위치에서 갈 수 있는 모든 곳을 먼저 확인한 후, 그 다음 깊이로 넘어간다고 생각하면 된다.

 

마찬가지로 미로 예시를 들면, 현재 위치에서 갈 수 있는 모든 방향을 다 시도해본 후에, 그 위치들에서 다시 갈 수 있는 모든 방향을 시도한다. 이렇게 레벨 단위로 탐색하는 방식이다. 이 방식은 큐(Queue) 자료구조를 사용해서 구현한다.

BFS(시작 노드):
    큐에 시작 노드 추가
    시작 노드 방문 표시
    큐가 빌 때까지:
        큐에서 노드 제거
        그 노드의 인접 노드 중에서:
            방문하지 않은 노드가 있으면:
                큐에 추가 후 방문 표시

 

BFS는 가깝다는 개념이 명확하다. 시작점에서 거리 1인 모든 노드를 먼저 방문하고, 그 다음 거리 2인 노드를 방문한다. 이 특성이 매우 중요하다.

DFS와 BFS의 실제 동작 비교

작은 그래프에서 두 방식이 어떻게 다르게 동작하는지 봐보자. 노드 A에서 출발해서 연결된 모든 노드를 방문한다고 가정하자.

 

DFS로 탐색하면 A → B → E → D → C → F → G → H 순서로 방문할 수 있다. 한 가지 경로를 깊이까지 파고든 후 다른 경로로 넘어가는 패턴이 보인다.

 

BFS로는 A → B, C → E, D, F → G, H 순서로 방문한다. 같은 거리의 노드들을 먼저 처리하고 더 먼 노드로 진행한다. 레벨 단위로 진행되는 것이 명확하다.

시간복잡도와 공간복잡도

두 알고리즘 모두 모든 노드를 한 번씩 방문한다. 따라서 시간복잡도는 동일하게 O(N+E)다. 여기서 N은 노드의 개수, E는 간선의 개수다.

 

노드를 방문할 때 인접한 노드들을 확인해야 한다. 이 인접 관계를 따라가는 데 간선의 개수만큼 연산이 필요하다. 그래서 간선의 개수가 시간복잡도에 포함된다. 모든 노드를 한 번씩 방문(N)하고 모든 간선을 한 번씩 확인(E)하므로 O(N+E)가 된다.

 

공간복잡도는 보조 자료구조가 최악의 경우 얼마나 많은 원소를 저장해야 하는지로 결정된다. DFS는 재귀 깊이가 깊어질 수 있고, BFS는 한 레벨의 모든 노드를 큐에 저장해야 할 수 있다. 두 경우 모두 O(N)의 공간이 필요하다. 다만 그래프의 구조에 따라 어느 것이 더 효율적일 수 있다. 넓고 얕은 그래프라면 BFS의 큐가 더 커질 것이고, 깊고 좁은 그래프라면 DFS의 재귀 스택이 더 커질 것이다.

각 알고리즘이 빛나는 상황들

코딩테스트 문제를 풀 때 어떤 것을 선택할지는 문제의 특성에 따라 달라진다. 단순히 "모든 노드를 방문하면 되는 문제"라면 둘 다 가능할 수 있지만, 더 효율적이거나 더 자연스러운 선택이 있다.

 

최단 경로를 구해야 할 때는 BFS가 필수다. BFS는 시작점에서 거리 1인 모든 노드를 확인 후 거리 2인 노드를 확인하는 식으로 진행되므로, 처음 도달한 노드가 최단 경로에서 도달하는 노드다. 따라서 가중치가 없는 그래프에서 최단 경로를 찾을 때 BFS를 사용하면 자연스럽게 최단 경로를 얻을 수 있다. 백준의 유명한 문제 '나이트의 이동' 같은 경우가 이에 해당한다.

 

연결된 요소의 개수를 세거나 사이클 존재 여부를 판단할 때는 DFS나 BFS 둘 다 사용 가능하다. 미로 찾기나 섬의 개수 세기 같은 문제도 마찬가지다. 하지만 코드의 간결함 측면에서는 보통 DFS(재귀)를 많이 사용한다. 재귀 호출 몇 줄로 깔끔하게 구현할 수 있기 때문이다.

 

경로 탐색이나 모든 가능한 경로를 찾아야 할 때도 DFS가 자연스럽다. 한 경로를 끝까지 파고드는 특성이 이런 문제에 잘 맞는다. 예를 들어 그래프에서 A에서 B까지 가는 모든 경로를 찾는다면, DFS로 한 경로를 끝까지 따라가서 경로를 기록하고 돌아나와 다른 경로를 시도하는 방식이 직관적이다.

BFS DFS 알고리즘 그래프 탐색

그래프 표현 방식의 선택

알고리즘 선택만큼 중요한 것이 그래프를 어떻게 자료구조에 담을 것인가다. 보통 인접 리스트(Adjacency List)를 사용한다. 노드 개수가 적고(1000개 미만) 간선이 많다면 인접 행렬(Adjacency Matrix)을 사용할 수도 있지만, 일반적으로는 인접 리스트가 더 효율적이다.

 

인접 리스트는 각 노드마다 연결된 이웃들을 리스트로 저장하는 방식이다. 필요한 메모리가 적고, 간선을 탐색할 때도 실제 연결된 간선들만 확인하면 되므로 효율적이다. 코딩테스트에서 그래프 문제를 풀 때는 대부분 이 방식으로 입력이 주어지거나, 입력받은 데이터를 이 방식으로 변환해서 풀게 된다.

실전 코딩테스트 팁

코딩테스트에서 그래프 문제를 풀 때 자주 하는 실수가 있다. 방문 표시를 제대로 안 하면 무한 루프에 빠진다. DFS는 재귀로 구현하든 스택으로 구현하든 현재 노드를 방문 표시해야 한다. BFS도 큐에 추가할 때 방문 표시를 하는 것이 중요하다. 안 그러면 같은 노드가 여러 번 큐에 추가될 수 있다.

 

또한 문제에서 시작 노드가 여러 개일 수 있다. 예를 들어 연결된 요소의 개수를 세는 문제라면, 아직 방문하지 않은 노드를 찾을 때마다 새로운 DFS나 BFS를 시작해야 한다. 반복문을 하나 더 감싸서 이를 처리한다.

 

그래프가 방향 그래프인지 무방향 그래프인지도 중요하다. 무방향 그래프면 간선을 양쪽으로 추가해야 한다. 이를 놓치면 실제로는 경로가 있는데 찾지 못하거나, 반대로 없는 경로를 있다고 판단할 수 있다.

문제 유형별 접근법

백준이나 프로그래머스에서 자주 나오는 유형들을 정리하면, 먼저 "최단 경로" 타입 문제가 있다. 가중치가 없고 단순히 거리만 중요하면 BFS를 쓴다. 가중치가 있으면 다익스트라나 벨만-포드 같은 다른 알고리즘이 필요하다.

 

"연결 관계" 타입도 많다. 몇 개의 연결된 요소가 있는지, 두 노드가 연결되어 있는지 등을 판단하는 문제들이다. 이런 경우 DFS나 BFS 둘 다 가능하지만, 문제의 조건에 따라 선택하면 된다.

 

"경로 탐색" 타입은 특정 조건을 만족하는 경로를 찾는 것이다. 모든 경로를 찾거나 특정 개수 이상의 경로를 세는 등의 문제가 여기 해당한다. 이런 경우는 DFS가 자연스럽다.

 

마지막으로 "레벨 단위 처리" 타입이 있다. 각 거리별로 따로 처리해야 하거나, 레벨별 정보가 필요한 경우다. BFS로 구현하면서 큐에서 꺼낼 때 현재 레벨의 모든 노드를 처리한 후 다음 레벨로 진행하는 식으로 하면 된다.

학습하면서 느낀 점

BFS와 DFS는 단순하지만 강력한 알고리즘이다. 많은 고급 알고리즘도 이 두 가지를 기본으로 한다. 따라서 이 둘을 완벽히 이해하는 것이 이후 알고리즘 학습의 기초가 된다. 처음에는 코드를 외워서 문제를 푸는 것도 좋지만, 시간이 지나면서 각 알고리즘이 언제 활용되는지, 왜 효율적인지를 이해하려고 노력해야 한다.

 

실제 코딩테스트를 준비하면서 느낀 것은, 문제를 읽을 때 "이건 탐색이 필요한 구나"라는 것을 먼저 파악하고, 그 다음에 "그럼 이건 깊이 우선으로 가야 할까, 너비 우선으로 가야 할까?"라는 판단을 한다는 것이다. 이 판단 과정이 자동으로 나올 때까지 여러 문제를 풀어보는 것이 중요하다. 같은 유형의 문제를 여러 번 풀면서 패턴을 익히다 보면, 나중에는 문제를 읽는 순간 어떤 알고리즘을 써야 할지가 떠오르게 된다.

 

코딩테스트 합격을 위한 스택·큐·덱 완벽 정리: 실전 문제 유형부터 구현 팁까지