그래프 - BFS vs DFS (너비 우선 탐색 vs 깊이 우선 탐색)

#1 차이의 핵심: 대기열

BFS와 DFS, 두 탐색 기법의 차이를 결정짓는 핵심은 '대기열' 관리다. 여기서 말하는 대기열을 영어로는 Frontier라고도 한다. 대기열이란 무엇인가? "다음에 갈 수 있는 곳들의 목록"이다. 이 대기열을 관리하는 방식의 차이가 곧 BFS 및 DFS 간의 차이다.

	BFS	DFS
대표 자료 구조	Queue	Stack
자료 구조의 성질	FIFO = 가장 오래 전 들어온 것을 꺼냄	LIFO = 가장 최근 들어온 것을 꺼냄
성질의 의미(Meaning)	발견 순서를 보존	발견 순서를 반전
의미(Meaning)에서 파생되는 결과 1	부모 쪽 처리가 먼저 확정(끝남)	자식 쪽 처리가 먼저 확정(끝남)
의미(Meaning)에서 파생되는 결과 2	대기열에 (대체로) 같은 층의 형제들이 담김	대기열에 (대체로) 조상들이 담김

 

#2 어떻게 판단하는가?

	BFS	DFS
일반적인 판단	답이 시작점으로부터의 거리에 의존할 때	답이 하위 구조에 의존할 때
예시(사례)	최단 거리	서브트리 크기(합) 연결 요소 크기 세기 위상 정렬 사이클 탐지 백트래킹 (경로를 쌓았다가 되돌려야 하므로 Stack 구조가 필수)
(잘) 못하는 것	후위 집계 (부모가 먼저 나오므로)	최단 거리 (첫 발견이 최적해가 아니므로)
(일반적으로) 둘 중 아무거나 써도 될 때	특정 정점에 닿는 지의 여부만을 참조 "방문했음" 표시 남기기 부모-자식 관계 라벨링

 

#3 형태가 아닌 기능을 봐야 한다.

BFS냐 DFS냐는 컴파일 시점에 (운명론적으로) 결정된다. 왜냐하면 대기열 구조를 결정하는 순간이 컴파일 시점이기 때문이다. 여기서 우리는 함정에 걸리고 만다. 아래 코드를 보자.

 

fun looksLikeBfs(startVertex: MyVertex) {
    val queue = ArrayDeque<MyVertex>()
    queue.add(startVertex)

    while (!queue.isEmpty()) {
        val vertex = queue.removeFirst()
        // TODO
    }
}

이 코드는 BFS일까 DFS일까? 겉보기엔 BFS다. 하지만 답은, "모른다"다. TODO 부분에 어떤 코드가 들어오냐에 따라, 이 BFS처럼 보이는 코드가 실제론 DFS 방식으로 동작할 수 있기 때문이다. 즉, 껍떼기 모양만으로 판단해선 안 된다. 이 게시글에서 구체적 사례를 다룬다.

 

#4 요약

BFS는 발견 순서를 보존하고, DFS는 발견 순서를 반전시킨다.