그래프 탐색 - 너비우선 탐색 (BFS Breadth-First Search) feat.kotlin

정의

 그래프를 방문 또는 탐색하는 방법중 하나이다.

시작 노드를 기준으로, "동일한 레벨"를 기준으로 탐색을 진행한다.

즉, 1개의 간선으로 연결된 모든 노드 탐색 후, 2개의 간선으로 연결된 모든 노드 탐색..

더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 탐색을 적용한다

 

한번 방문한 노드는 다시 방문하지 않는다.

 

V - 정점(노드)의 개수

E - 간선의 개수 

 

인접리스트로 표현된 자료구조로 탐색 했다면

시간복잡도 -  O(V + E)

 

인접행렬로 표현된 자료구조로 탐색 했다면 (시간 복잡도가 크기 때문에 인접리스트로 바꾸어 탐색)

시간복잡도 O(V^2)

 

동일한 level 순으로 탐색을 해야될때 사용한다.

간선에 특별한 가중치가 있지 않고 모든 간선의 가중치가 동일하다면, 시작 노드로 부터 최단거리를 구할수 있다.

Queue를 통한 구현

// 그래프 탐색 BFS

val dist = IntArray(6) { 0 }
val visited = BooleanArray(6) { false }

val queue: Queue<Int> = LinkedList()

fun bfs(g: List<List<Int>>, u: Int) {
    
    dist[u] = 1
    visited[u] = true
    queue.add(u)

    while (queue.isNotEmpty()) {
        val v = queue.peek()
        queue.poll()
        println(v)
        for (u in g[v]) {
            if (!visited[u]) {
                visited[u] = true
                dist[u] = dist[v]+1
                queue.add(u)
            }
        }
    }
}

fun main() {

    val vNum = 6
    val adjList = MutableList(vNum) { mutableListOf<Int>() }
    adjList[1] = mutableListOf(2, 4)
    adjList[2] = mutableListOf(1, 3)
    adjList[3] = mutableListOf(2, 5)
    adjList[4] = mutableListOf(1, 5)
    adjList[5] = mutableListOf(3, 4)

    bfs(adjList, 5)
    println(visited.joinToString())
    println(dist.joinToString())
}

/*
 map 탐색 BFS
 맵의 특정 위치는 y(row) x(col)로 좌표로 나타낸다.
 Pair<Int, Int> 또는 2개의 Int Type 파라미터를 필요로 한다.
 아래 코드는 맵을 탐색하면서 연결된 덩어리 지역을 방문을 표기한다.
*/

val map = arrayOf (
    arrayOf(1,0,1,1,1,1),
    arrayOf(1,0,1,0,1,0),
    arrayOf(1,0,1,0,1,1),
    arrayOf(1,1,1,0,1,1)
)

val dy = arrayOf(-1, 0, 1, 0)
val dx = arrayOf(0, 1, 0, -1)

val rows = 4
val cols = 6
val dist = Array(rows) { IntArray(cols) { 0 } }

val q: Queue<Pair<Int, Int>> = LinkedList()

fun mBfs(p: Pair<Int, Int>) {

    dist[p.first][p.second] = 1
    q.add(p)

    while (q.isNotEmpty()) {

        val p = q.peek()
        q.poll()

        for (i in 0 until 4) {
            val ny = p.first + dy[i]
            val nx = p.second + dx[i]

            // 맵을 벗어나면 안됨
            if (ny !in 0 until map.size || nx !in 0 until map.first().size) continue
            // 재방문은 허용되지 않음
            if (dist[ny][nx] != 0) continue
            // 길이 아니면 안됨
            if (map[ny][nx] == 0) continue
            dist[ny][nx] = dist[p.first][p.second] + 1
            q.add(ny to nx)
        }
    }
}

fun main() {
    mBfs(0 to 0)
    dist.forEach {
       println(it.joinToString())
    }
}