한국어
메뉴

너비 우선 탐색과 깊이 우선 탐색의 차이: 방문 순서·자료 구조·최단 경로·메모리·용도 비교

둘 다 그래프나 트리의 정점을 간선을 따라 빠짐없이 방문하는 탐색 방법입니다. 너비 우선 탐색(BFS)은 출발점에서 간선 1개로 갈 수 있는 정점을 모두 방문한 뒤 2개로 갈 수 있는 정점으로 가는 식으로, 가까운 순서대로 퍼져 나갑니다. 깊이 우선 탐색(DFS)은 한 경로를 갈 수 있는 데까지 나아가고, 막다른 곳에 이르면 되돌아와 다른 경로로 나아갑니다. 너비 우선 탐색은 큐로, 깊이 우선 탐색은 스택이나 재귀로 구현하며, 인접 리스트로 나타낸 그래프라면 둘 다 정점 수와 간선 수의 합에 비례하는 시간으로 전체를 방문합니다. 간선에 가중치가 없는 그래프의 최단 경로를 구할 때는 너비 우선 탐색, 모든 경로를 남김없이 조사하는 처리나 사이클 검출에는 깊이 우선 탐색이 자주 쓰입니다.

비교 항목너비 우선 탐색(BFS)깊이 우선 탐색(DFS)
방문 순서출발점에서 가까운 순서(거치는 간선 수가 적은 순서)로 층마다 퍼져 나간다한 경로를 끝까지 나아가고, 막다른 곳에 이르면 되돌아와 다음 경로로 나아간다
사용하는 자료 구조큐(선입선출)스택(후입선출) 또는 재귀 호출
최단 경로간선에 가중치가 없는 그래프에서는 처음 도달했을 때의 간선 수가 출발점으로부터의 최단 거리가 된다최단이 보장되지 않는다. 돌아가는 경로로 먼저 도달할 수 있다
계산량(정점 수 V, 간선 수 E)인접 리스트에서는 O(V + E), 인접 행렬에서는 O(V²)너비 우선 탐색과 마찬가지로 인접 리스트에서는 O(V + E), 인접 행렬에서는 O(V²)
사용하는 메모리다음에 방문할 정점을 큐에 저장해 둔다. 가지가 많으면 한 층의 정점이 한꺼번에 큐에 들어가 커진다재귀로 쓰면 지금 따라가는 경로 위의 정점만 기억하면 되므로 경로의 깊이에 비례한다. 너무 깊으면 콜 스택이 넘칠 수 있다
해를 찾는지 여부정점이 유한하면 반드시 찾는다. 탐색 범위가 한없이 넓어지는 경우에도 얕은 위치의 해부터 차례로 찾는다유한 그래프에서 방문한 정점을 기록하면 반드시 찾는다. 한없이 깊어지는 경우에는 한 경로를 계속 나아가 돌아오지 못할 수 있다
트리 순회 순서레벨 순서(루트에서 가까운 단마다 왼쪽에서 오른쪽으로)전위 순회, 중위 순회, 후위 순회
주요 용도가중치 없는 그래프의 최단 경로, 미로의 최소 이동 횟수, 네트워크에서 몇 단계 앞까지 닿는지의 계산미로나 퍼즐의 모든 경우의 탐색(백트래킹), 연결 요소나 사이클의 검출, 위상 정렬

수치는 대략적인 자릿수 기준이며, 공정 세대와 제품에 따라 달라져요.

상황별 선택 기준

너비 우선 탐색
간선에 가중치가 없는 그래프에서 최소 이동 횟수나 최단 경로를 구하고 싶을 때, 출발점 가까이부터 차례로 조사하고 싶을 때 적합합니다. 간선에 가중치가 있을 때의 최단 경로에는 다익스트라 알고리즘을 씁니다.
깊이 우선 탐색
모든 경로나 조합을 남김없이 조사하고 싶을 때, 연결 요소나 사이클을 찾고 싶을 때, 작업 순서를 정하는 위상 정렬을 할 때 적합합니다. 재귀로 짧게 쓸 수 있습니다.

자주 묻는 질문

간선에 가중치가 있을 때도 너비 우선 탐색으로 최단 경로를 구할 수 있나요?

구할 수 없습니다. 거치는 간선 수가 가장 적은 경로가 가중치의 합도 가장 작다고는 할 수 없기 때문입니다. 가중치가 0 이상이면 다익스트라 알고리즘을 씁니다. 다익스트라 알고리즘은 큐 대신 출발점으로부터의 거리가 작은 정점부터 꺼내는 우선순위 큐를 쓰는 방법으로, 너비 우선 탐색을 가중치 있는 그래프로 확장한 것으로 볼 수도 있습니다.

깊이 우선 탐색은 재귀와 스택 중 어느 쪽으로 쓰면 좋나요?

재귀로 쓰면 짧고 이해하기 쉽지만, 매우 깊은 그래프에서는 호출이 겹쳐 콜 스택이 넘칠 수 있습니다. 스택을 직접 준비해 반복문으로 쓰면 이를 피할 수 있습니다. 다만 이웃 정점을 스택에 쌓는 순서에 따라 재귀와 방문 순서가 달라질 수 있습니다.

방문한 정점을 기록하지 않으면 어떻게 되나요?

사이클이 있는 그래프에서는 같은 정점을 몇 번이고 방문하게 됩니다. 너비 우선 탐색에서는 큐가 한없이 커지고, 깊이 우선 탐색에서는 같은 사이클을 계속 돌아 끝나지 않을 수 있습니다. 그래서 어느 방법이든 방문한 정점(또는 큐나 스택에 넣은 정점)에 표시를 해 두 번 다시 넣지 않도록 합니다.

이해도 확인

간선에 가중치가 없는 그래프에서, 출발점에서 각 정점까지의 최소 간선 수를 구하고 싶다. 적합한 탐색 방법과 그때 사용하는 자료 구조의 조합은?

  1. A너비 우선 탐색과 큐
  2. B깊이 우선 탐색과 스택
  3. C너비 우선 탐색과 스택
정답과 해설 보기

정답: A. 너비 우선 탐색과 큐

너비 우선 탐색은 출발점에서 간선 1개로 갈 수 있는 정점, 2개로 갈 수 있는 정점…처럼 가까운 순서로 방문합니다. 발견한 정점을 큐의 뒤에 넣고 앞에서 꺼내어 조사함으로써 이 '가까운 순서'가 유지되므로, 처음 도달했을 때의 간선 수가 그대로 최소 수가 됩니다. 깊이 우선 탐색(재귀나 스택을 사용)은 한 길을 갈 수 있는 데까지 나아가므로, 돌아가는 경로로 먼저 도달하는 경우가 있어 최단이 보장되지 않습니다. 큐 대신 스택을 사용하면 깊이 우선 탐색에 가까운 순회가 되어 버립니다.

간선에 방향이 없는 그래프에서 각 정점의 이웃 정점이 다음과 같다. A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. 정점 A부터 재귀적인 깊이 우선 탐색을 수행한다. 이웃 정점은 여기에 쓴 순서로 조사하고, 아직 방문하지 않은 정점이 발견되면 바로 그 정점으로 나아간다. 정점을 방문하는 순서는?

  1. AA, B, C, D, E, F
  2. BA, B, D, E, C, F
  3. CA, B, D, E, F, C
정답과 해설 보기

정답: C. A, B, D, E, F, C

A에서 B로 나아가고, B의 이웃 중 처음으로 방문하지 않은 D로 나아갑니다. D의 이웃은 방문한 B뿐이므로 B로 돌아가 다음 E로 나아가고, E에서 방문하지 않은 F로, F에서 그 이웃인 C로 나아갑니다. 따라서 A, B, D, E, F, C의 순서입니다. A, B, C, D, E, F는 출발점에서 가까운 순서로 방문하는 너비 우선 탐색의 순서입니다. A, B, D, E, C, F는 E에서 방문하지 않은 F로 나아가지 않고 돌아가 버렸으므로 깊이 우선 탐색의 순서가 되지 않습니다.

정점이 100만 개, 간선이 300만 개 정도인 도로망처럼 정점 수에 비해 간선이 적은(희소한) 그래프를 메모리에 저장하는 방법으로 적절한 것은?

  1. A인접 행렬. 두 정점 사이에 간선이 있는지를 O(1)로 조사할 수 있고, 기억 영역도 가장 적게 든다
  2. B인접 리스트. 기억 영역은 정점 수와 간선 수의 합에 비례하며, 어떤 정점에서 나가는 간선을 차례로 따라가는 데 적합하다
  3. C인접 행렬. 기억 영역은 간선 수에만 비례한다
정답과 해설 보기

정답: B. 인접 리스트. 기억 영역은 정점 수와 간선 수의 합에 비례하며, 어떤 정점에서 나가는 간선을 차례로 따라가는 데 적합하다

인접 행렬은 정점 수 V에 대해 V×V의 표를 사용하므로, 100만 정점에서는 10¹²개의 원소가 필요하며 원소 하나를 1비트로 해도 약 125 GB가 됩니다. 인접 리스트는 각 정점에 이어진 정점만 나열하므로 기억 영역은 O(V + E)이며, 이 예라면 수백만 건 정도로 충분합니다. 인접 행렬은 간선의 유무를 O(1)로 조사할 수 있는 이점이 있어, 간선이 많은(밀집한) 그래프나 정점이 적은 그래프에 적합합니다. 너비 우선 탐색이나 다익스트라 알고리즘처럼 정점에서 나가는 간선을 차례로 따라가는 처리에서는 인접 리스트가 더 효율적으로 동작합니다.

  1. 간선에 방향이 없는 그래프에서 간선의 가중치(거리)가 S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3, A−T: 6이다. 다익스트라 알고리즘으로 S에서 T까지의 최단 경로를 구했을 때, 그 경로와 길이는?
  2. 빈 이진 탐색 트리에 50, 30, 70, 20, 40, 60, 80의 순서로 값을 삽입했다. 이 트리를 후위 순회(왼쪽 서브트리, 오른쪽 서브트리, 그 노드 순으로 방문한다)로 따라갔을 때의 순서는?

자료 구조와 알고리즘 문제 풀기

주요 용어 설명

너비 우선 탐색(Breadth-First Search)
그래프나 트리를 출발점에서 가까운 순서(간선 1개로 갈 수 있는 정점, 다음으로 2개로 갈 수 있는 정점…)로 방문하는 탐색 방법. 큐를 사용하여 구현하며, 간선에 가중치가 없는 그래프에서는 출발점에서 각 정점까지의 최소 간선 수가 구해진다. 영어 머리글자로 BFS라고도 한다.
깊이 우선 탐색(Depth-First Search)
그래프나 트리를, 한 길을 갈 수 있는 데까지 나아가고 막다른 곳에 이르면 되돌아와 다른 길로 나아가는 순서로 방문하는 탐색 방법. 재귀나 스택으로 구현하며, 미로 탐색, 연결 요소나 사이클의 검출, 위상 정렬 등에 쓰인다. 영어 머리글자로 DFS라고도 한다.
큐(Queue)
가장 먼저 넣은 원소를 가장 먼저 꺼내는 선입선출(FIFO) 자료 구조. 뒤에 넣는 조작을 인큐, 앞에서 꺼내는 조작을 디큐라고 한다. 처리 대기열, 태스크 간의 데이터 주고받기, 너비 우선 탐색 등에 쓰인다.
스택(Stack)
마지막에 넣은 원소를 가장 먼저 꺼내는 후입선출(LIFO) 자료 구조. 원소를 쌓는 조작을 push, 꺼내는 조작을 pop이라고 한다. 함수 호출의 복귀 주소나 지역 변수의 관리(콜 스택), 역폴란드 표기법의 수식 계산, 깊이 우선 탐색 등에 쓰인다.
재귀(Recursion)
함수가 처리 도중에 자기 자신을 호출하는 것. 문제를 같은 형태의 작은 문제로 나누어 풀고, 더 이상 나누지 않는 경우(기저 사례)에서 호출을 끝낸다. 호출마다 스택을 사용하므로 너무 깊으면 넘친다. 마지막에 자신을 호출하기만 하는 꼬리 재귀는 루프로 변환할 수 있다.
다익스트라 알고리즘(Dijkstra's Algorithm)
간선의 가중치가 0 이상인 그래프에서, 하나의 출발점에서 각 정점까지의 최단 경로를 구하는 알고리즘. 거리가 확정되지 않은 정점 중 가장 가까운 것을 확정하고, 그 이웃 정점의 거리를 갱신하는 것을 반복한다. 음의 가중치를 가진 간선이 있으면 올바르게 구할 수 없다.
시간 복잡도(Time Complexity)
알고리즘에 필요한 수고(시간 복잡도)나 기억 영역(공간 복잡도)이 데이터의 수 n에 대해 어떻게 늘어나는지를 나타낸 것. O(n)이나 O(n log n), O(n²) 같은 점근 표기법(빅오 표기법)으로, 계수나 낮은 차수의 항을 생략하여 쓴다.

관련 비교