DFS? BFS?
DFS와 BFS는 그래프 탐색 알고리즘을 대표하는 알고리즘입니다.
두 알고리즘 모두 그래프의 모든 노드를 탐색하는 방법 중 하나이지만 무엇을 우선적으로 탐색하는지에 따라 달라지게 됩니다.
DFS는 Depth First Search로 그래프에서 깊이를 우선적으로 탐색하는 알고리즘입니다.
BFS는 Breadth First Search로 그래프에서 너비를 우선적으로 탐색하는 알고리즘입니다.
DFS (Depth First Search)
DFS는 깊이를 우선적으로 탐색하는 알고리즘으로, 노드의 한 방향으로 갈 수 있는 만큼 최대한 깊이 들어가면서 탐색합니다.
DFS 알고리즘은 그래프에서 경로를 탐색하는 문제나, 백트래킹 문제 등에서 사용할 수 있습니다.
일반적으로 DFS 알고리즘을 구현할 때는 스택이나 재귀함수를 이용해 구현합니다.
DFS 알고리즘 과정 (재귀)
재귀를 이용하여 DFS 알고리즘을 구현하는 과정은 다음과 같습니다.
-
노드 정보를 바탕으로 그래프를 생성합니다.
-
노드의 방문 여부를 저장할 수 있는 배열을 생성합니다.
-
시작 노드에서부터 시작하여 DFS 재귀 함수를 호출합니다.
-
호출된 DFS 함수에서는 다음과 같은 과정을 반복합니다.
- 현재 노드를 방문했다고 표시합니다.
- 현재 노드와 인접한 모든 노드를 탐색합니다.
- 만약 방문하지 않은 노드가 있다면 해당 노드에서 DFS 재귀 함수를 호출 합니다.
이 과정을 코틀린 코드로 구현하면 아래와 같습니다.
// graph : 노드 정보를 바탕으로 생성한 그래프입니다.
// visit : 노드의 방문 여부를 저장하고 있는 배열입니다.
// visitOrder : 방문 순서를 저장하는 배열입니다.
// node : 현재 탐색중인 노드를 의미합니다.
fun dfs(
graph: Array<MutableList<Int>>,
visit: BooleanArray,
visitOrder: MutableList<Int>,
node: Int,
) {
// 현재 노드를 방문했다고 표시합니다.
visit[node] = true
// 방문 순서 배열에 현재 노드를 추가합니다.
visitOrder.add(node)
// 현재 노드와 인접한 모든 노드를 탐색합니다.
for (i in graph[node]) {
// 만약 방문하지 않은 노드가 있다면 해당 노드에서 dfs 재귀 함수를 호출합니다.
if (!visit[i]) dfs(graph, visit, visitOrder, i)
}
}visitOrder와 같이 방문 순서를 저장할 배열을 추가하면 dfs의 노드 탐색 순서를 알 수 있습니다.
BFS (Breadth First Search)
BFS는 너비를 우선적으로 탐색하는 알고리즘으로, 시작 노드로부터 모든 인접한 노드를 먼저 탐색하고, 그 다음으로 인접한 노드들의 인접한 노드를 순차적으로 방문하며 탐색합니다.
때문에 BFS 알고리즘은 시작 노드에서 목표 노드까지의 최단 경로를 구하는 경우에 사용할 수 있습니다.
일반적으로 BFS 알고리즘은 큐를 이용해 구현합니다.
BFS 알고리즘 과정
큐를 사용하여 BFS 알고리즘을 구현하는 과정은 다음과 같습니다.
-
노드 정보를 바탕으로 그래프를 생성합니다.
-
노드의 방문 여부를 저장할 수 있는 배열을 생성합니다.
-
큐를 생성하고 시작 노트를 큐에 추가합니다.
-
시작 노드를 방문했다고 표시합니다.
-
큐가 빌 때까지 아래 과정을 반복합니다.
- 큐에서 노드를 꺼냅니다.
- 현재 노드와 인접한 모든 노드를 탐색합니다.
- 만약 방문하지 않은 노드가 있다면 해당 노드를 큐에 추가하고, 방문했다고 표시합니다.
이 과정을 코틀린 코드로 구현하면 아래와 같습니다.
// graph : 노드 정보를 바탕으로 생성한 그래프입니다.
// start : 시작 노드를 의미합니다.
fun bfs(
graph: Array<MutableList<Int>>,
start: Int
): IntArray {
// 방문 여부 및 방문 순서를 저장하는 배열입니다.
val visit = IntArray(graph.size) { -1 }
// 큐를 LinkedList를 사용해 선언합니다.
val queue = LinkedList<Int>()
// 방문 순서를 기록할 변수입니다.
var visitCount = 1
// 시작 노드를 방문했다고 표시합니다.
visit[start] = visitCount++
// 시작 노드를 큐에 추가합니다.
queue.add(start)
// 큐가 비어있지 않은 동안 반복합니다.
while (queue.isNotEmpty()) {
// 큐에서 노드를 꺼냅니다.
val c = queue.poll()!!
// 현재 노드와 인접한 모든 노드를 탐색합니다.
for (i in graph[c]) {
// 방문하지 않은 노드가 있다면 큐에 추가하고, 방문했다고 표시합니다.
if (visit[i] == -1) {
visit[i] = visitCount++
queue.add(i)
}
}
}
return visit
}visitCount를 통해 방문 순서를 기억하고 visit 배열에 저장하면 bfs의 노드 탐색 순서를 알 수 있습니다.
