30초 답변

DFS와 BFS는 그래프나 트리를 방문하는 대표적인 탐색 방법입니다. DFS는 Stack이나 재귀를 사용해 가능한 깊이까지 들어갔다가 돌아옵니다. BFS는 Queue를 사용해 시작점에서 가까운 노드부터 탐색합니다. 최단 간선 수가 중요한 unweighted graph에서는 BFS가 자연스럽고, 모든 경우의 수나 연결 요소 탐색에는 DFS가 자주 쓰입니다.

꼬리질문

조금 더 깊게 물어본다면

답변 뒤에 이어질 수 있는 질문들을 하나씩 열어볼 수 있어요.

1

2

3

4

5

DFS는 어떤 자료구조로 구현하나요?

재귀 호출을 사용하거나 명시적인 Stack을 사용합니다. 재귀는 내부적으로 call stack을 사용합니다.

이전 질문다음 꼬리질문

부가 설명

미로를 생각하면 DFS는 한 갈림길을 끝까지 가 본 뒤 막히면 돌아오는 방식입니다. BFS는 현재 위치에서 한 칸 거리, 두 칸 거리처럼 가까운 곳부터 넓게 확인합니다. 둘 다 모든 노드를 방문할 수 있지만, 방문 순서가 다르기 때문에 잘 맞는 문제가 달라집니다.

특히 “최단 거리”라는 말이 나오면 가중치가 없는 그래프인지 먼저 봐야 합니다. 모든 간선 비용이 같다면 BFS는 처음 도착한 순간이 최단 거리입니다. 하지만 간선마다 비용이 다르면 단순 BFS가 아니라 다익스트라 같은 알고리즘을 고려해야 합니다.

한 줄 정리

DFS는 깊게, BFS는 가깝게 탐색한다는 차이를 문제 조건에 연결해야 합니다.