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

너비 우선 탐색(breadth first search, BFS)은 탐색 시작 노드로부터 가장 가까운 노드부터 탐색하는 그래프 탐색 알고리즘이다. 탐색 시작 노드와 하나의 간선으로 연결된 노드에서 찾고자 하는 노드가 있는지 먼저 확인한다. 탐색 시작 노드에서 가장 가까운 노드에서 찾고자 하는 노드가 있는지 먼저 확인해야 하므로 탐색 후보 노드를 선입선출(first in first out)로 관리하기 위해 큐(queue) 자료 구조를 사용한다.

인접한 노드를 큐에 넣고 먼저 넣은 노드를 먼저 꺼내 탐색하므로 루트 노드로부터 가까이 위치한 노드부터 탐색한다. 너비 우선 탐색은 재귀 함수 호출을 사용하여 구현하기는 어려우며 큐 자료 구조를 직접 사용하여 구현할 수 있다.

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

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

너비 우선 탐색은 시작 노드를 시작점으로 하여 시작 노드에서 가장 가까운 인접 노드부터 하나씩 순차적으로 탐색한다. 반복문을 사용하여 시작 노드부터, 시작 노드에서 인접한 노드를 먼저, 시작 노드에서 멀리 떨어진 노드를 가장 나중에 큐 자료 구조에 저장한다.

너비 우선 탐색은 기본적으로 탐색한 노드를 다시 탐색하지 않는다. 따라서 반복문 호출을 종료하는 조건은 다음과 같다.

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

반복문의 실행 로직은 다음과 같다.

• 큐에서 노드를 꺼냄
• 현재 노드를 방문 처리
• 인접한 노드를 큐에 추가

노드를 방문 처리하는 과정은 현재 노드를 탐색했으니 더 이상 탐색할 필요가 없음을 메모리 상에 기록하는 것이다. 노드를 큐에 넣는 과정은 노드 탐색 대상을 관리하기 위해 메모리 상에 기록하는 것이다. 큐에서 노드를 꺼내는 과정은 메모리 상에 기록된 순서대로 노드를 탐색하는 것이다. 큐에서 노드를 꺼내는 순서가 노드 탐색 순서가 된다.

너비 우선 탐색의 과정은 다음과 같다.

1. 시작 노드를 방문 처리한다.
2. 시작 노드를 큐에 넣는다.
3. 큐가 비어있지 않는 동안 다음 과정을 반복 처리한다:
    3-1. 큐에서 노드를 꺼낸다.
    3-2. 꺼낸 현재 노드의 모든 이웃 노드에 대해 다음 과정을 반복 처리한다:
        3-2-1. 유효한 이웃 노드인지 확인한다.
        3-2-2. 아직 방문하지 않은 이웃 노드인지 확인한다.
        3-2-3. 노드 탐색을 하지 않는 특정 조건을 만족하지 않는지 확인한다.
        3-2-4. 위 조건을 모두 만족하는 경우 이웃 노드를 방문 처리하고 큐에 넣는다.

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

class BFS {
    // 이중 배열
    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) // (상하 없음), 왼쪽, 오른쪽

    // 각 노드의 좌표를 저장하기 위한 데이터 클래스
    data class Node(val r: Int, val c: Int)

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

        println("BFS 시작:")
        startBFS(0, 0)
    }

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

    private fun bfs(r: Int, c: Int) {
        val queue: Queue<Node> = LinkedList()

        // 시작점을 큐에 추가하고 방문 처리
        queue.offer(Node(r, c))
        visited[r][c] = true

        // 큐가 비어있지 않은 동안 반복
        while (queue.isNotEmpty()) {
            // 큐에서 노드를 하나 꺼냄
            val currentNode = queue.poll()

            val currentR = currentNode.r
            val currentC = currentNode.c

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

                // 반복문 호출 종료 조건 확인

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

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

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

                // 방문 처리
                visited[nextR][nextC] = true 

                // 큐에 다음 노드 추가
                queue.offer(Node(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)와 같은 트리 탐색 문제를 해결하기 위해 너비 우선 탐색을 사용할 수 있다. 너비 우선 탐색은 여러 종류의 트리 순회 중 레벨 순서 순회(level-order traversal) 문제를 해결하는데 사용된다.

참고