너비 우선 탐색은 그래프에서 가장 가까운 노드부터 순서대로 방문하는 알고리즘입니다. 이 알고리즘은 큐(queue) 자료 구조를 사용하여 구현합니다. 큐는 먼저 들어온 데이터가 먼저 나가는 구조로, 새로운 요소는 항상 큐의 뒤쪽(rear)에 추가되고, 요소를 제거할 때는 앞쪽(front)에서 제거됩니다.

큐(queue) 자료 구조

큐는 너비 우선 탐색에서 사용하는 가장 중요한 자료 구조 중 하나입니다.

class Queue<T> {
    private val elements = mutableListOf<T>()

    fun enqueue(element: T) {
        elements.add(element)
    }

    fun dequeue(): T? {
        if (elements.isEmpty()) {
            return null
        }
        return elements.removeAt(0)
    }

    fun isEmpty(): Boolean {
        return elements.isEmpty()
    }
}

위의 코드는 제네릭을 이용하여 큐를 구현한 예시입니다. Kotlin에서 필요에 따라 큐를 직접 구현할 수도 있고, 내장된 Queue 인터페이스를 활용할 수도 있습니다.

너비 우선 탐색에서 큐는 노드를 방문한 순서대로 저장하고, 먼저 들어온 노드를 먼저 방문하도록 돕습니다. 이를 통해 모든 인접 노드를 방문한 후에 다음 단계의 노드로 이동할 수 있게 합니다.

맺음말

너비 우선 탐색에서는 큐 자료 구조를 사용하여 그래프를 순차적으로 탐색합니다. 큐는 먼저 들어온 요소가 먼저 처리되는 선입선출(FIFO) 방식으로 구현되어야 하며, 다양한 방식으로 구현이 가능합니다.