깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

1. 깊이 우선 탐색 (DFS)

 

1.1 개념

탐색 시작 노드로부터 한 방향으로 나아가 마지막 노드를 찍고 다음 분기로 넘어가는 것.
위 방법을 통해 해당 분기를 완벽하게 탐색하는 방식.

 

1.2 동작 방식

1. 탐색 시작 노드를 스택에 넣고 방문(BooleanArray[node] = true) 처리를 한다.
2. 최상단 노드 인근에 방문하지 않는 노드가 있다면 해당 노드를 스택에 넣으며 방문처리를 한다.
 - 인접 노드가 여러 개 있다면 번호가 낮은 순으로 처리
 - 인접 노드가 전부 방문한 노드라면 최상단 노드 꺼내기
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복.

 

1.3 적용

1. 길 찾기
2. 미로
3. 경로의 특징을 저장해야하는 경우

 

1.4 구현

val dfsList = mutableListOf<Int>()

fun dfs(node: Int, visited: BooleanArray, tree: Array<MutableList<Int>>) {
    visited[node] = true
    dfsList.add(node)
    tree[node].forEach { if (!visited[it]) dfs(it, visited, tree) }
}

 

예시로 작성된 구현 방식으로, 재귀와 반복문을 이용해 방문처리를 하며 노드의 끝까지 갔다 오는 방식이다.

스택의 원리와 재귀함수의 개념을 이용해 구현이 가능하며 시작 노드에서부터 방문처리를 하며 스택에 넣고,

 - 인접한 노드 중 방문하지 않은 노드가 존재한다면 해당 노드를 스택에 넣고 방문 처리.

 - 인접한 노드 중 방문하지 않은 노드가 없다면 위치한 노드의 스택을 빼면서 다시 처음으로 복귀

 

 

 

2. 너비 우선 탐색 (BFS)

 

1.1 개념

탐색 시작 노드로부터 인접한 노드를 먼저 탐색하는 방식.
시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어진 노드를 나중에 방문하는 순회 방법이다.

 

1.2 동작 방식

1. 탐색 시작 노드를 큐에 넣고 방문(BooleanArray[node] = true) 처리를 한다.
2. 큐에서 노드를 꺼내 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 넣고 방문처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복.

 

1.3 적용

1. 길 찾기, 라우팅
2. 최단거리를 구해야하는 문제
3. SNS 멀리 떨어진 사람 찾기
4. Graph에서 주변 위치 찾기

 

1.4 구현

val bfsList = mutableListOf<Int>()

fun bfs(node: Int, visited: BooleanArray, tree: Array<MutableList<Int>>) {
    val queue = ArrayDeque<Int>()
    visited[node] = true
    queue.add(node)
    bfsList.add(node)
    
    while (queue.isNotEmpty()) {
        val current = queue.removeFirst()
        tree[current].forEach { 
            if (!visited[it] && !queue.contains(node)) {
                visited[it] = true
                queue.add(it)
                bfsList.add(it)
            }
        }
    }
}

 

예시로 작성된 구현 방식으로, 큐와 반복문을 통해 방문처리를 하며 탐색을 한다.

큐와 반복문을 통해 구현이 가능하며, 큐에 맨 처음 원소를 하나씩 빼며 처리를 한다.

 

 

위 두 알고리즘을 활용함에 있어 다음을 유의하면 좋다.

 - 검색 대상 그래프가 크다면 DFS를 고려할 것.

 - 검색 대상 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS를 고려할 것.