BFS와 DFS 알고리즘이란 무엇이며 언제 어떻게 선택할까?
BFS와 DFS는 그래프에서 한 시작 정점으로부터 갈 수 있는 정점을 체계적으로 찾아가는 탐색 알고리즘입니다. BFS는 가까운 정점부터 층별로 넓혀 가므로 무가중치 그래프의 최소 간선 수 경로가 필요할 때 적합하고, DFS는 한 갈래를 끝까지 따라간 뒤 되돌아오므로 구조 분석, 사이클 검사, 위상 정렬 같은 문제의 기반으로 쓰입니다. 어느 쪽이 항상 더 좋은 것은 아니며, 경로의 기준과 그래프의 목적에 따라 선택해야 합니다. ocw.mit.edualgs4.cs.princeton.edu
그래프 탐색에서 BFS와 DFS는 무엇을 찾나요?
그래프는 정점과 간선으로 이루어진 관계 구조입니다. 정점은 사람, 도시, 웹페이지, 작업처럼 개체를 나타내고, 간선은 친구 관계, 도로, 링크, 선행 관계처럼 둘 사이의 연결을 나타냅니다. 정점 집합을 , 간선 집합을 로 표기합니다.
간선에 방향이 없으면 무방향 그래프입니다. 예를 들어 서로 친구라는 관계는 보통 양방향으로 생각할 수 있습니다. 반대로 A가 B를 팔로우한다거나 작업 A가 작업 B보다 먼저 끝나야 한다는 관계는 방향 그래프가 됩니다. 방향 그래프에서는 화살표 방향을 따라갈 수 있을 뿐, 반대 방향으로 자동 이동할 수는 없습니다. ocw.mit.edu
그래프 탐색의 가장 기본적인 질문은 “시작점 에서 어떤 정점에 도달할 수 있는가”입니다. BFS와 DFS는 이 질문에 답하면서, 방문 여부, 각 정점에 처음 도달한 경로, 탐색 순서 같은 부가 정보도 남길 수 있습니다. 다만 시작점 하나에서 출발한 탐색은 그 시작점에서 실제로 도달 가능한 부분만 처리합니다. 그래프의 모든 정점을 반드시 방문한다는 뜻은 아닙니다. ocw.mit.edu
트리도 그래프의 한 종류입니다. 따라서 폴더 구조나 조직도처럼 트리로 보이는 문제에도 BFS와 DFS를 사용할 수 있습니다. 그러나 일반 그래프에는 한 정점으로 돌아오는 사이클과 여러 경로가 있을 수 있다는 점이 중요합니다. 트리 탐색만 염두에 둔 구현을 일반 그래프에 그대로 적용하면 중복 방문 문제가 생길 수 있습니다.
BFS는 가까운 정점부터 어떻게 탐색하나요?
BFS는 Breadth-First Search, 즉 너비 우선 탐색의 약자입니다. 시작점에서 간선 하나로 갈 수 있는 정점을 먼저 찾고, 그 다음 간선 두 개로 갈 수 있는 정점, 그 다음 세 개가 필요한 정점 순으로 탐색 범위를 넓힙니다. 여기서 거리는 물리적 거리나 비용이 아니라, 시작점에서 지나야 하는 간선 수입니다. algs4.cs.princeton.edu
이를 위해 BFS는 보통 큐를 사용합니다. 큐는 먼저 들어온 항목이 먼저 나오는 FIFO(First In, First Out) 자료구조입니다. 시작점을 큐에 넣고 방문 표시를 한 뒤, 큐의 앞에서 정점을 하나 꺼냅니다. 그 정점의 아직 발견하지 않은 이웃을 모두 방문 표시하고 큐의 뒤에 넣습니다. 이후 큐가 빌 때까지 같은 일을 반복합니다. 먼저 발견된 가까운 정점들이 먼저 처리되므로 층별 확장이 유지됩니다. gh.cp-algorithms.comalgs4.cs.princeton.edu
예를 들어 A에서 시작해 A의 이웃 B, C를 발견했다고 하겠습니다. BFS는 B를 처리할 때 B의 이웃을 발견하고, 이어 C를 처리할 때 C의 이웃을 발견합니다. B에서 발견한 정점이 더 깊은 곳에 있더라도, 이미 큐에 들어간 같은 레벨의 C가 먼저 또는 그에 준해 처리되는 흐름이 만들어집니다. 정확한 B와 C의 선후 관계는 인접 정점의 저장 순서에 따라 달라질 수 있습니다.
BFS의 핵심은 “발견 즉시 방문 표시”입니다. 큐에서 꺼낼 때까지 표시를 미루면, 두 정점이 같은 이웃을 각각 발견해 큐에 중복 삽입할 수 있습니다. 일반적인 BFS에서는 새 이웃을 큐에 넣는 바로 그 시점에 발견됨으로 표시하는 편이 단순하고 안전합니다.
BFS가 최단 경로를 제공하는 조건은 무엇인가요?
BFS가 특히 자주 선택되는 이유는 무가중치 그래프에서 시작점으로부터 각 도달 가능한 정점까지의 최소 간선 수 경로를 구하기 때문입니다. 시작점에서 한 단계 떨어진 정점을 모두 확인한 다음 두 단계 떨어진 정점을 확인하므로, 어떤 정점을 처음 발견한 경로보다 간선 수가 더 적은 경로가 나중에 나타날 수 없습니다. BFS 중 각 정점을 처음 발견한 직전 정점을 부모로 기록하면, 그 부모 포인터들이 최단 경로 트리를 이룹니다. algs4.cs.princeton.edu
경로를 복원하려면 목표 정점에서 부모를 거꾸로 따라가 시작점까지 이동한 뒤 순서를 뒤집으면 됩니다. 예를 들어 parent[D] = B, parent[B] = A라면 A에서 D로 가는 발견 경로는 A → B → D입니다. 시작점의 부모는 따로 없다는 표식을 둡니다.
그러나 “최단”이라는 말을 넓게 해석하면 오류가 생깁니다. BFS가 보장하는 것은 모든 간선의 비용을 동일하게 취급할 수 있을 때의 최소 간선 수입니다. 도로마다 이동 시간이 다르거나 항공편마다 요금이 다르면, 간선 두 개를 지나는 경로가 간선 한 개를 지나는 경로보다 더 싸거나 더 빠를 수 있습니다. 이 경우 일반 BFS는 비용 기준 최단 경로 알고리즘이 아닙니다. 가중치의 성질에 따라 다익스트라 알고리즘이나 벨만-포드 알고리즘처럼 가중치를 다루는 별도 방법을 검토해야 합니다. algs4.cs.princeton.edu
따라서 “친구를 몇 단계 거치면 연결되는가”, “격자에서 상하좌우 한 칸 이동을 한 번으로 볼 때 몇 번 만에 도착하는가”처럼 이동 횟수가 같은 단위인 문제에는 BFS가 잘 맞습니다. 반면 “가장 적은 시간”이나 “가장 낮은 비용”이 목표라면 간선 가중치가 정말 같은지부터 확인해야 합니다.
DFS는 왜 깊게 들어갔다가 되돌아오나요?
DFS는 Depth-First Search, 즉 깊이 우선 탐색입니다. 현재 정점에서 방문하지 않은 이웃 하나를 골라 계속 이동하고, 더 갈 곳이 없어질 때까지 한 분기를 깊게 탐색합니다. 막다른 곳에 이르면 바로 이전 정점으로 돌아가 아직 탐색하지 않은 다른 이웃을 찾습니다. 이런 되돌아감 과정을 백트래킹이라고 부르기도 합니다. ocw.mit.edu
DFS는 재귀 호출로 구현하기 쉽습니다. 어떤 정점에 들어오면 먼저 방문 표시를 하고, 그 정점의 이웃 가운데 미방문 정점마다 같은 탐색 함수를 호출합니다. 재귀 호출이 끝날 때마다 자연스럽게 호출한 지점으로 돌아오므로 깊게 들어갔다가 되돌아오는 제어 흐름이 표현됩니다.
재귀가 유일한 방법은 아닙니다. 스택을 직접 두고 반복문으로 구현할 수도 있습니다. 스택은 마지막에 넣은 항목이 먼저 나오는 LIFO(Last In, First Out) 자료구조입니다. 최근에 발견한 정점을 우선 꺼내면 깊이 우선의 흐름을 만들 수 있습니다. 재귀 방식에서는 프로그램의 호출 스택이 이 역할을 암묵적으로 수행합니다. ocw.mit.edugh.cp-algorithms.com
DFS가 만든 부모 포인터도 시작점에서 정점까지의 경로 하나를 알려 줄 수 있습니다. 하지만 그 경로가 최소 간선 수 경로라는 보장은 없습니다. DFS는 먼저 선택한 분기를 가능한 한 깊게 따라가므로, 더 짧은 경로가 다른 분기에 있더라도 나중에 발견할 수 있습니다. ocw.mit.edu
DFS는 어떤 구조 분석에 쓰이나요?
DFS의 진가는 단순 도달 가능성보다 그래프의 구조를 분석할 때 드러납니다. 연결 요소 탐색이 대표적입니다. 무방향 그래프에서 임의의 미방문 정점에서 DFS를 한 번 수행하면, 그 정점과 연결된 정점들을 모두 하나의 묶음으로 찾습니다. 남은 미방문 정점에서 다시 DFS를 시작하면 다른 묶음을 찾을 수 있습니다.
사이클 탐지도 DFS의 대표적인 활용입니다. 사이클은 간선을 따라가다 다시 출발점 또는 이미 경로 안에 있는 정점으로 돌아올 수 있는 구조입니다. 방향 그래프에서는 탐색 중인 현재 재귀 경로에 이미 있는 정점을 만났는지 구분하는 방식으로 사이클을 판정할 수 있습니다. 단순히 ‘한 번 방문한 정점’만 표시하는 것과, ‘현재 탐색 경로 위에 있는 정점’을 구분해야 하는 이유가 여기에 있습니다.
위상 정렬은 작업 사이의 선행 관계처럼 방향성을 가진 의존성을 순서로 나열하는 작업입니다. 방향 비순환 그래프, 즉 DAG(Directed Acyclic Graph)에서만 가능합니다. DAG는 방향을 따라가도 시작점으로 되돌아오는 사이클이 없는 방향 그래프입니다. 사이클이 있다면 A 전에 B, B 전에 A를 끝내야 하는 식의 모순이 생기므로 모든 간선을 만족하는 선형 순서를 만들 수 없습니다. DFS의 종료 순서를 활용하는 방법은 위상 정렬의 한 기반입니다. algs4.cs.princeton.edu
강연결 요소 탐색 역시 DFS를 바탕으로 하는 중요한 주제입니다. 강연결 요소는 방향 그래프에서 같은 묶음의 임의의 두 정점이 서로에게 도달 가능한 정점들의 집합입니다. 다만 이 문제는 단순 DFS 한 번만으로 끝나는 것이 아니라, 탐색 순서와 그래프의 간선 방향을 활용하는 알고리즘적 구성이 필요합니다. algs4.cs.princeton.edu
방문 표시가 없으면 어떤 문제가 생기나요?
일반 그래프에서 방문 표시 배열이나 집합은 선택 사항이 아니라 종료와 정확성을 위한 핵심 장치입니다. 예를 들어 A와 B가 서로 연결되어 있을 때 A에서 B로 간 뒤 B에서 다시 A로 갈 수 있습니다. 방문 여부를 확인하지 않으면 DFS는 A와 B를 재귀적으로 계속 오갈 수 있고, BFS도 같은 정점을 여러 번 큐에 넣을 수 있습니다. ocw.mit.edu
방문이라는 말은 구현에 따라 약간 다르게 나뉩니다. BFS에서는 보통 정점을 큐에 넣는 순간 ‘발견됨’으로 표시합니다. DFS에서는 함수에 처음 들어가는 순간 방문 표시를 하는 방식이 흔합니다. 더 정교한 방향 그래프 분석에서는 아직 미방문인 상태, 현재 탐색 중인 상태, 탐색이 완료된 상태를 구분하기도 합니다.
정점을 한 번만 방문한다는 원칙은 탐색 효율에도 직접 연결됩니다. 이미 처리한 정점을 다시 확장하지 않으면, 인접 리스트 기준으로 각 정점과 간선을 제한된 횟수만 확인하게 됩니다. 또한 부모 포인터를 처음 발견했을 때만 정하면, 어느 경로가 그 정점을 최초로 발견했는지가 명확해집니다.
그래프 전체를 탐색하려면 바깥 반복문이 필요합니다. 모든 정점을 차례로 보면서 아직 방문하지 않은 정점을 찾을 때마다 BFS나 DFS를 새로 시작합니다. 무방향 그래프에서는 이것으로 연결 요소별 탐색이 되고, 방향 그래프에서는 선택한 간선 방향으로 도달 가능한 범위들을 차례로 처리하게 됩니다. ocw.mit.edu
시간 복잡도는 그래프 표현에 따라 왜 달라지나요?
BFS와 DFS의 시간 복잡도는 흔히 라고 말합니다. 이는 인접 리스트를 사용할 때의 표준적인 분석입니다. 인접 리스트는 각 정점마다 직접 연결된 이웃 목록을 저장합니다. 방문 표시가 있으면 정점은 한 번 처리되고, 각 이웃 목록을 훑으며 간선을 확인하므로 전체 작업량이 정점 수와 간선 수의 합에 비례합니다. ocw.mit.edu
추가 공간은 보통 입니다. 방문 배열, 부모 배열, BFS의 큐 또는 DFS의 스택이 이에 해당합니다. 재귀 DFS라면 재귀 호출 깊이에 따른 호출 스택도 추가 공간에 포함됩니다. 그래프 자체를 저장하는 공간과 탐색 알고리즘이 추가로 쓰는 공간은 구분해서 생각하는 것이 좋습니다. ocw.mit.edu
인접 행렬은 정점 쌍마다 간선 존재 여부를 표 형태로 저장합니다. 어떤 정점의 이웃을 찾으려면 가능한 모든 정점을 검사해야 할 수 있습니다. 그래서 인접 행렬에서 BFS나 DFS를 수행하면 보통 시간이 걸릴 수 있습니다. 간선이 적은 희소 그래프에서는 실제 연결된 이웃만 훑는 인접 리스트가 특히 효율적입니다. ocw.mit.edu
| 표현 방식 | 이웃 확인 방식 | 탐색 시간의 일반적 형태 |
|---|---|---|
| 인접 리스트 | 실제로 연결된 이웃 목록을 순회 | |
| 인접 행렬 | 가능한 모든 정점과의 연결을 검사 |
복잡도 표기는 입력 크기가 커질 때의 증가 경향을 설명합니다. 실제 실행 시간은 정점 식별 방식, 인접 리스트 구현, 메모리 배치, 탐색 시작점에서 도달 가능한 부분의 크기에도 영향을 받습니다. 그래도 알고리즘을 고를 때는 먼저 그래프가 희소한지, 그리고 어떤 표현으로 저장되어 있는지를 확인하는 것이 합리적입니다.
BFS와 DFS의 실제 방문 순서는 하나로 정해지나요?
정해지지 않습니다. BFS는 가까운 레벨을 먼저 처리하고 DFS는 현재 분기를 깊게 처리한다는 원칙을 갖지만, 같은 레벨 안에서 어느 정점을 먼저 방문하는지, 여러 이웃 중 어느 갈래로 먼저 내려가는지는 인접 정점의 저장 순서에 좌우됩니다. gh.cp-algorithms.comgh.cp-algorithms.com
예를 들어 A의 이웃 목록이 B, C 순서이면 BFS는 일반적으로 B를 먼저 발견합니다. 목록을 C, B로 바꾸면 C가 먼저 발견될 수 있습니다. DFS에서는 이 차이가 더 크게 이어질 수 있습니다. 처음 선택한 이웃이 달라지면 깊게 탐색하는 분기 자체가 달라지고, 부모 포인터로 만든 탐색 트리와 DFS 경로도 달라질 수 있습니다.
이 사실은 알고리즘의 결과를 평가할 때 중요합니다. 문제에서 “사전순으로 가장 먼저 방문되는 순서”를 요구하면 인접 목록을 정렬하거나 우선순위 규칙을 명시해야 합니다. 반대로 단순히 도달 가능 여부, 연결 요소 개수, 최소 간선 수 거리만 필요하다면 같은 레벨 또는 같은 깊이에서의 세부 순서는 결과의 핵심이 아닐 수 있습니다.
특히 DFS를 스택으로 반복 구현할 때는 이웃을 스택에 넣는 순서와 실제 꺼내는 순서가 반대가 될 수 있습니다. 재귀 구현의 인접 목록 순서와 같은 방문 순서를 원한다면, 스택에 이웃을 넣는 방향을 의도적으로 조정해야 합니다. 이는 DFS의 정의가 달라진 것이 아니라 LIFO의 작동 방식에서 나오는 구현상 차이입니다.
흔한 오해와 실수는 무엇인가요?
첫째, BFS는 모든 종류의 최단 경로를 푼다는 오해입니다. 앞서 본 것처럼 BFS는 무가중치 그래프에서 최소 간선 수를 보장합니다. 가중치가 서로 다르면 ‘한 번 이동’과 ‘한 번 이동’의 값이 같지 않으므로 문제 모델부터 달라집니다. algs4.cs.princeton.edualgs4.cs.princeton.edu
둘째, DFS는 BFS보다 항상 메모리를 적게 쓴다는 단정입니다. 두 알고리즘 모두 방문 배열과 탐색 상태를 포함하면 일반적으로 의 추가 공간을 사용할 수 있습니다. 특정 그래프 모양과 구현에서는 큐나 스택의 최대 크기가 다르게 나타날 수 있지만, 점근적 복잡도만으로 무조건적인 우열을 정할 수는 없습니다. ocw.mit.edu
셋째, 재귀 DFS는 어떤 입력에서도 안전하다는 생각입니다. 깊이가 매우 긴 그래프에서는 재귀 깊이도 길어집니다. 사용하는 언어와 실행 환경의 호출 스택 제한에 걸릴 가능성을 고려해야 하며, 이런 경우 명시적 스택을 쓰는 반복 구현이 실용적일 수 있습니다. 재귀 호출 스택이 DFS의 추가 공간이라는 점도 함께 이해할 필요가 있습니다. ocw.mit.edu
넷째, 방향 그래프를 무방향 그래프처럼 취급하는 실수입니다. A에서 B로 향하는 간선이 있다고 해서 B에서 A로 갈 수 있는 것은 아닙니다. 입력을 인접 리스트에 저장할 때도 무방향 그래프는 보통 양쪽 목록에 추가하지만, 방향 그래프는 출발 정점의 목록에만 추가합니다. 이 차이는 도달 가능성, 연결성, 사이클의 의미를 바꿉니다. ocw.mit.edu
다섯째, 탐색 결과를 ‘유일한 정답 경로’로 오해하는 것입니다. BFS는 최소 간선 수가 같은 경로가 여러 개일 때 그중 하나를 부모 포인터로 기록합니다. DFS도 이웃 순서에 따라 서로 다른 경로를 만들 수 있습니다. 경로 자체의 우선순위가 필요하다면 정렬 규칙이나 추가 조건을 문제에 명시해야 합니다.
문제를 만났을 때 무엇을 기준으로 선택하면 되나요?
가장 먼저 목표를 문장으로 바꾸는 것이 좋습니다. “시작점에서 갈 수 있는가”만 묻는다면 BFS와 DFS 모두 가능하며, 구현 환경과 뒤이어 필요한 분석을 고려해 고를 수 있습니다. “몇 번의 동일한 이동으로 도착하는가”처럼 최소 간선 수가 필요하면 BFS가 자연스럽습니다. “한 경로를 깊게 따라가며 구조를 분석해야 하는가”, “되돌아오는 시점이 의미가 있는가”라면 DFS가 적합할 가능성이 큽니다.
다음으로 간선의 의미를 확인합니다. 모든 이동이 같은 비용인가, 아니면 시간·거리·비용 같은 가중치가 있는가를 구분해야 합니다. 가중치가 있다면 BFS의 최단 경로 성질을 그대로 적용하지 않습니다. 또한 그래프가 방향 그래프인지, 사이클이 가능한지, 전체 그래프를 봐야 하는지도 미리 확인합니다. ocw.mit.edualgs4.cs.princeton.edu
선택 기준을 간단히 정리하면 다음과 같습니다.
| 상황 또는 질문 | 우선 검토할 방법 | 주의할 조건 |
|---|---|---|
| 최소 이동 횟수, 레벨별 확장 | BFS | 간선 비용이 동일해야 함 |
| 단순 도달 가능성 | BFS 또는 DFS | 시작점에서 닿는 부분만 탐색함 |
| 연결 요소를 묶어 찾기 | DFS 또는 BFS | 미방문 정점마다 탐색을 반복함 |
| 사이클, 위상 정렬, 강연결 구조 분석 | DFS 기반 방법 | 위상 정렬은 DAG에서만 가능함 |
| 시간·비용이 서로 다른 최단 경로 | 다른 가중치 최단 경로 방법 | 일반 BFS의 보장이 적용되지 않음 |
마지막으로 입력 크기와 표현 방식을 봅니다. 희소 그래프라면 인접 리스트와 표준 BFS·DFS의 분석이 잘 들어맞습니다. 재귀 깊이가 문제가 될 수 있는 환경에서는 반복 DFS를 고려할 수 있습니다. 방문 순서가 채점이나 업무 규칙에 영향을 준다면 인접 목록의 순서도 설계의 일부가 됩니다.
결론: 이름보다 탐색 목표와 조건이 먼저입니다
BFS와 DFS는 그래프를 빠짐없이 탐색하기 위한 서로 다른 전략입니다. BFS는 큐를 이용해 가까운 정점부터 확장하며, 무가중치 그래프에서 최소 간선 수 경로를 제공한다는 강점이 있습니다. DFS는 재귀나 스택으로 한 갈래를 깊게 탐색하고 되돌아오며, 연결 요소, 사이클, DAG의 위상 정렬처럼 그래프 구조를 다루는 여러 방법의 토대가 됩니다. ocw.mit.edualgs4.cs.princeton.edu
둘 다 방문 표시가 필요하고, 인접 리스트 기준으로는 보통 같은 점근적 시간 복잡도를 갖습니다. 따라서 선택의 핵심은 속도라는 이름표 하나가 아니라, 최단 경로의 기준이 무엇인지, 간선에 가중치가 있는지, 방향과 사이클을 어떻게 해석해야 하는지, 전체 그래프를 처리해야 하는지에 있습니다. 이 조건을 먼저 구분하면 BFS와 DFS를 목적에 맞게 사용할 수 있습니다.