[자료 구조/알고리즘] 깊이 우선 탐색 구현

깊이 우선 탐색(depth first search, DFS)은 탐색 시작 노드로부터 가장 멀리 위치한 노드부터 탐색하는 그래프 탐색 알고리즘이다. 탐색 시작 노드에서 가장 멀리 위치한 노드에서 찾고자 하는 노드가 있는지 먼저 확인해야 하므로 탐색 후보 노드를 후입선출(last in first out)로 관리하기 위해 스택(stack) 자료 구조를 사용한다.

인접한 노드를 스택 자료 구조에 넣고 나중에 넣은 노드를 먼저 꺼내 탐색하므로 루트 노드로부터 가장 멀리 위치한 노드부터 탐색한다. 깊이 우선 탐색은 재귀 함수 호출을 사용하거나 스택 자료 구조를 직접 사용하여 구현할 수 있다.

그래프 탐색 문제는 일반적으로 이중 배열을 사용하여 구현할 수 있다. 이 때, 이중 배열의 각 원소를 노드로, 인접한 원소 사이를 간선으로 간주한다.

재귀 함수 호출을 사용한 구현

깊이 우선 탐색은 시작 노드를 시작점으로 하여 시작 노드에서 가장 멀리 위치한 노드부터 탐색한다. 재귀 호출을 사용하여 시작 노드부터 시작하여 시작 노드에서 가장 멀리 위치한 노드 사이의 경로에 존재하는 모든 노드를 먼저 탐색한다.

깊이 우선 탐색은 기본적으로 탐색한 노드를 다시 탐색하지 않는다. 따라서 재귀 함수 호출을 종료하는 기본 단계는 다음과 같다.

• 노드 탐색 범위를 벗어난 경우 (배열의 인덱스 범위를 벗어난 경우)
• 이미 방문한 노드일 경우
• 노드 탐색을 하지 않는 특정 조건을 만족하는 경우 (예: 탐색 대상 노드 발견, 목적지 발견 등)

재귀 함수의 실행 로직은 다음과 같다.

• 현재 노드를 방문 처리
• 인접한 노드에 대해 재귀적으로 탐색

노드를 방문 처리하는 과정은 현재 노드를 탐색했으니 더 이상 탐색할 필요가 없음을 메모리 상에 기록하는 것이다. 인접한 노드에 대해 재귀적으로 함수를 호출하는 과정은 노드를 스택 자료 구조에 넣는 과정과 동일하며 이는 노드 탐색 대상을 관리하기 위해 메모리 상에 기록하는 것이다. 재귀 함수 호출 과정은 메모리 상에 기록된 순서대로 노드를 탐색하는 것이다. 재귀 함수 호출 순서가 노드 탐색 순서가 된다.

깊이 우선 탐색을 사용하여 이중 배열에서 값이 1인 원소를 모두 탐색하는 구현은 다음과 같다.

class DFS {
    // 이중 배열
    private lateinit var grid: Array<IntArray>
    
    // 노드 방문 기록 배열
    private lateinit var visited: Array<BooleanArray>
    private var rows: Int = 0
    private var cols: Int = 0

    // 상하좌우 이동을 위한 델타 배열
    private val dr = intArrayOf(-1, 1, 0, 0) // 위, 아래, (좌우 없음)
    private val dc = intArrayOf(0, 0, -1, 1) // (상하 없음), 왼쪽, 오른쪽

    fun solve(inputGrid: Array<IntArray>) {
        this.grid = inputGrid
        this.rows = grid.size
        this.cols = grid[0].size
        this.visited = Array(rows) { BooleanArray(cols) }

        println("DFS 시작:")
        startDFS(0, 0)
    }

    private fun startDFS(startRow: Int, startCol: Int) {
        // 노드 탐색 시작점 유효성 확인
        if (startRow in 0 until rows && startCol in 0 until cols && grid[startRow][startCol] == 1) {
            dfs(startRow, startCol)
        } else {
            println("유효하지 않은 노드 탐색 시작점입니다.")
        }
    }

    private fun dfs(r: Int, c: Int) {
        // 1. 재귀 함수 호출 종료 조건 확인 (기본 단계)

        // a. 노드 탐색 범위를 벗어나는 경우
        if (r !in 0 until rows || c !in 0 until cols) {
            return
        }

        // b. 이미 방문한 노드인 경우
        if (visited[r][c]) {
            return
        }

        // c. 노드 탐색을 하지 않는 조건을 만족하는 경우
        if (grid[r][c] != 1) {
            return
        }

        // 2. 현재 노드 방문 처리
        visited[r][c] = true

        // 3. 인접 노드 모두 탐색 (상하좌우)
        for (i in 0 until 4) {
            val nextR = r + dr[i]
            val nextC = c + dc[i]

            // 재귀 호출
            dfs(nextR, nextC)
        }
    }
}

fun main() {
    val myGrid = arrayOf(
        intArrayOf(1, 1, 0, 0, 0),
        intArrayOf(1, 1, 0, 1, 0),
        intArrayOf(0, 0, 0, 1, 0),
        intArrayOf(0, 0, 0, 1, 1)
    )

    val solver = DFS()
    solver.solve(myGrid)
}

스택 자료 구조와 반복문을 사용한 구현

트리 자료 구조 탐색 구현

깊이 우선 탐색은 그래프 탐색을 해결하는 알고리즘이지만, 트리 자료 구조 또한 그래프의 한 형태이므로 트리 순회(tree traversal)와 같은 트리 탐색 문제를 해결하기 위해 깊이 우선 탐색을 사용할 수 있다.

참고