[알고리즘] 그래프 탐색(DFS, BFS)

정의

그래프(graph)란 정점(Node)과 간선(Edge)으로 이루어진 자료구조이며, 이 안에서 특정 노드를 방문하는 순서를 정의하고 구현하는 알고리즘을 그래프 탐색(graph traversal)이라고 합니다.

 

DFS(깊이 우선 탐색): 한 노드를 깊이(끝)까지 계속 탐색한 후, 더 이상 갈 곳이 없으면 되돌아가서 다른 경로를 탐색하는 방식

• 갈 수 있는 곳까지 계속 깊이 들어감
• 막히면 되돌아와서 다른 방향을 탐색
• 보통 재귀함수로 구현

fun dfs(graph: Array<MutableList<Int>>, visited: BooleanArray, v: Int) {
    visited[v] = true
    println("방문: $v")  // 현재 노드 출력

    for (i in graph[v]) {  // 현재 노드에 연결된 노드들 중
        if (!visited[i]) { // 아직 방문하지 않은 노드만
            dfs(graph, visited, i) // 재귀 호출
        }
    }
}

BFS(너비 우선 탐색): 한 노드에서 시작해서 가까운 노드부터 차례로 탐색하는 방식 (즉, 레벨 순으로 탐색)

• 시작 노드에서 가까운 노트부터 차례로 방문
• 즉, "레벨별로" 넓게 탐색
• 최단 거리 문제에 매우 유리함

import java.util.*

fun bfs(graph: Array<MutableList<Int>>, visited: BooleanArray, start: Int) {
    val queue: Queue<Int> = LinkedList()
    queue.add(start)
    visited[start] = true

    while (queue.isNotEmpty()) {
        val v = queue.poll()
        println("방문: $v")

        for (i in graph[v]) {
            if (!visited[i]) {
                queue.add(i)
                visited[i] = true
            }
        }
    }
}

 

 

DFS와 BFS 개념 비교

	DFS(Depth - First Search)	BFS(Breadth-First Search)
접근 방식	깊이 우선 (먼저 끝까지 내려감)	너비 우선 (가까운 노드부터 탐색)
자료구조	스택(Stack) (보통은 재귀로 구현)	큐(Queue)
구현 방식	재귀 또는 명시적 스택 사용	큐를 이용한 반복문
경로 탐색	경로를 추적하기 쉬움 (백트래킹)	최단 경로 문제에 유리함

 

따라서

• 모든 경로를 다 봐야 하는 문제 👉 DFS
• 최단 거리, 레벨 기반 탐색  👉 BFS
• 경로 추적 / 백트래킹 필요  👉 DFS
• 효율적인 탐색(큐 기반)  👉 BFS

문제별로 어떤 방법을 사용할지 선택하는게 중요합니다.