2020-12-29

BFS(Breadth-First Search)

미로를 탐색하는 방법의 일종이다. BFS는 큐를 이용하는데, 방문한 위치에서 사방으로 이동 가능한 모든 위치를 큐에 삽입하고 방문했다고 표시한 후, 현재 위치를 큐에서 제거한다.
written by

큐를 이용한 미로 탐색 알고리즘

미로를 탐색하는 방법의 일종이다. BFS는 큐를 이용하는데, 방문한 위치에서 사방으로 이동 가능한 모든 위치를 큐에 삽입하고 방문했다고 표시한 후, 현재 위치를 큐에서 제거한다. 그리고 큐에 존재하는 노드들을 순서대로 방문하면서 위의 과정을 반복한다.

이렇게 하면 분기점에서 한 방향으로 끝까지 탐색한 후에 목적지가 없다면 다시 분기점으로 돌아와서 다른 방향으로 탐색을 진행할 수 있다.

이 방법은 모든 위치를 방문하기 전에 목적지를 찾는다면 검색을 종료하므로 일반적으로 빠르게 탐색을 종료할 수 있다. 깊게 탐색하기 전에 전체적으로 같은 깊이를 탐색하므로 최단거리를 보장하게 된다.

단점은 큐를 이용하므로 큐를 저장하는 메모리를 많이 쓰게 된다. 미로의 규모가 크다면 메모리의 크기를 고려해야 한다.

Algorithm

시작 지점을 큐에 Push 하고 방문했다고 표시한다. 동서남북의 이동 가능한 위치를 전부 큐에 Push 한다. 이제 방문했다고 표시한 현재 위치를 큐에서 Pop 한다. 이렇게 하면 다음으로 이동 가능한 위치가 큐에 순서대로 존재한다. 현재 위치를 큐의 head 위치로 옮겨주고, 위의 과정을 반복한다.

Kotlin Code

import java.util.*

// 1. List: 완전 불변, 추가 X/수정 X
// 2. Array: 조건부 가변, 추가 X/수정 O
// 3. MutableList: 완전 가변, 추가 O/수정 O
// + 초깃값 선언: listOf(value, value2, ...) }
// + 초깃값 선언식: List(size) { index -> expression }
// + mutableListOf<T>()로 선언문만으로 초기화 가능
// + 나머지는 반드시 초깃값이 필요

// 0이면 통로, 1이면 벽으로 간주하는 맵.
// 가로는 열(col), 세로는 행(row), map[row][col]로 위치 표시.
val map = arrayOf(
    intArrayOf(0, 1, 0, 0, 1, 0),
    intArrayOf(0, 0, 0, 1, 0, 1),
    intArrayOf(0, 1, 0, 0, 0, 0),
    intArrayOf(1, 0, 0, 1, 0, 1),
    intArrayOf(1, 0, 0, 1, 0, 0),
)

// 해당 map 위치의 방문 여부를 의미한다.
val visit = arrayOf(
    booleanArrayOf(false, false, false, false, false, false),
    booleanArrayOf(false, false, false, false, false, false),
    booleanArrayOf(false, false, false, false, false, false),
    booleanArrayOf(false, false, false, false, false, false),
    booleanArrayOf(false, false, false, false, false, false),
)

// map 시작 지점 및 현재 위치와 도착 지점.
val currentPosition = intArrayOf(0, 0)
val goalPosition = intArrayOf(4, 5)

// row 좌표는 -1은 북쪽, +1은 남쪽.
// col 좌표는 -1은 서쪽, +1은 동쪽.
val directions = listOf(
    Pair(0, -1),
    Pair(0, 1),
    Pair(-1, 0),
    Pair(1, 0),
)

// BFS 방문을 위한 탐색 큐. 탐색 큐에 삽입하여 초기화한다.
val bfsQueue = LinkedList<IntArray>().apply {
    push(currentPosition)
}

// 도착 지점에 도착할 때까지 탐색한다.
// 탐색 큐가 다 비어도 도착 지점을 찾지 못하면, 경로가 없다.
// 기본적인 흐름은 분기점을 만나면 길이 막힐 때까지 길 찾기를 진행한 후에,
// 못 찾으면 분기점으로 돌아와서, 다음 길을 방문한다.
while (bfsQueue.isNotEmpty()) {

    // 탐색 큐에서 탐색 중인 위치를 현재 위치로 저장하고 방문한 것으로 표시.
    currentPosition[0] = bfsQueue.element()[0]
    currentPosition[1] = bfsQueue.element()[1]
    visit[currentPosition[0]][currentPosition[1]] = true

    // 맵을 출력한다.
    printMap(map, currentPosition)

    // 탐색 큐에서 제거하여 탐색을 진행.
    bfsQueue.pop()

    // 현재 위치가 목적지라면 탐색을 종료.
    if (currentPosition.contentEquals(goalPosition)) {
        break
    }

    // 아니라면 사방으로 방문이 가능한지 판별해서 방문하고 큐에 삽입한다.
    // 큐는 선입선출(FIFO)이므로 마지막에 방문한 곳이 헤드(HEAD)를 가리켜 다음 위치가 됨.
    directions.forEach { direction ->

        // 다음으로 이동할 row, col
        val movePositionRow = currentPosition[0] + direction.first
        val movePositionCol = currentPosition[1] + direction.second

        // 다음으로 이동할 위치가 맵을 벗어나지 않는지 확인한다.
        if (movePositionRow >= 0 && movePositionRow < map.size && movePositionCol >= 0 && movePositionCol < map[0].size) {

            // 다음으로 이동할 위치가 벽이 아니고, 방문한 적이 없는지 확인하고 탐색 큐에 삽입.
            if (map[movePositionRow][movePositionCol] == 0 && !visit[movePositionRow][movePositionCol]) {
                bfsQueue.push(intArrayOf(movePositionRow, movePositionCol))
            }
        }
    }
}

// 맵을 문자로 표현하여 출력하는 함수.
// 벽은 X, 통로는 빈 문자, 현재 위치는 *로 표시한다.
fun printMap(map: Array<IntArray>, currentPosition: IntArray) {
    Array(map.size) { i ->
        Array(map[i].size) { j ->
            when {
                map[i][j] == 0 -> "[ ]"
                else -> "[X]"
            }
        }
    }.apply {
        this[currentPosition[0]][currentPosition[1]] = "[*]"
    }.run {
        println("--------------------")
        forEach { eachRow ->
            eachRow.forEach { eachCell ->
                print(eachCell)
            }.run { println("") }
        }
        println("--------------------")
    }
}

Result

--------------------
[*][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[*][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[*][X][ ][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][*][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][*][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][*][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][*][X][ ][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][*][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][*][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][*][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][*][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][*][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][*][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][X][*][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][*][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][*]
--------------------
2021 © Cinntiq's Studio