2020-12-29

너비 우선 탐색(BFS, Breadth-First Search)

BFS(Breadth-First Search)는 큐를 이용한 방법으로 구현한다. 재밌게도 스택을 이용해서 구현한 DFS 미로 탐색에서 큐로 바꾸기만 하면 된다.
written by

Introduction

미로의 출발 지점부터 도착 지점까지 가는 방법은 무엇이 있을까?

우리가 커다란 미로에 갇혀 있다면 지나간 길을 표시하면서 가다가 이미 갔던 길이라면 되돌아와서 지나가지 않은 길을 가야 할 것이다. 그러면 어디로 갈지를 결정하고 어디로 되돌아 갈지를 결정해야 한다. 이제 미로를 탐색하는 두 가지 규칙을 정하자.

  • 갈 수 있는 모든 방향으로 다 가보고 각각의 갈 수 있는 모든 지점들을 후보로 기록한다.
  • 모든 후보 지점으로 가서 위의 과정을 도착 지점을 찾을 때까지 반복한다.

이런 방법으로 가다 보면 모든 경로에 대해서 같은 거리만큼을 계속 전진하면서 미로를 탐색하게 된다. 이 방식이 BFS(Breadth-First Search)의 원리이다.

이 방식의 장점은 모든 경로를 같은 거리로 탐색하기 때문에 도착 지점으로 가는 경로가 있다면 최단 경로임을 보장한다는 것이다.

Algorithm

BFS(Breadth-First Search)는 큐를 이용한 방법으로 구현한다.

우선 시작 지점을 스택에 넣고 방문한 것으로 표시한다.

  • 방문할 수 있는 모든 후보 지점을 큐에 넣고 방문한 것으로 표시한다.
  • 큐의 헤드를 현재 위치로 옮겨 준 후에 큐에서 제거한다.
  • 방문한 곳은 건너뛰고 위의 과정을 경로를 발견할 때까지 반복한다.

재밌게도 스택을 이용해서 구현한 DFS 미로 탐색에서 큐로 바꾸기만 하면 된다.

Kotlin Scratch Code

import java.util.*

// 0이면 통로, 1이면 벽으로 간주하는 이차원 배열이다.
// 가로는 열(col), 세로는 행(row), maze[row][col]로 위치를 표시한다.
val maze = listOf(
    listOf(0, 1, 0, 0, 1, 0),
    listOf(0, 0, 0, 1, 0, 1),
    listOf(0, 1, 0, 0, 0, 0),
    listOf(1, 0, 0, 1, 0, 1),
    listOf(1, 0, 0, 1, 0, 0),
)

// 해당 maze[row][col] 지점의 방문 여부를 의미한다.
val visit = listOf(
    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),
)

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

// 방문한 것으로 표시한 시작 지점과 도착 지점을 배열에 저장한다.
val location = intArrayOf(0, 0).also { visit[it[0]][it[1]] = true }
val goal = intArrayOf(4, 5)

// 시작 지점을 삽입하여 Maze 탐색 큐를 초기화한다.
val mazeQueue = ArrayDeque<IntArray>().apply { add(location) }

// 큐가 다 비어도 도착 지점을 찾지 못하면 경로가 없다.
while (mazeQueue.isNotEmpty()) {

    // 큐에서 탐색 중인 위치를 현재 위치로 저장하고 큐에서 제거한다.
    location[0] = mazeQueue.element()[0]
    location[1] = mazeQueue.element()[1]
    mazeQueue.poll()

    // 미로를 출력한다.
    printMaze(maze, location)

    // 현재 위치가 목적 지점이라면 탐색을 종료한다.
    if (location.contentEquals(goal)) {
        break
    } else {

        // 사방으로 방문이 가능한지 판별한다.
        directions.forEach { direction ->

            // 방문할 지점이 맵을 벗어나지 않는지 확인한다.
            if (location[0] + direction.first >= 0 && location[0] + direction.first < maze.size && location[1] + direction.second >= 0 && location[1] + direction.second < maze[0].size) {

                // 방문할 지점이 벽이 아니고, 방문한 적이 없는지 확인한 후에 큐에 삽입하고 방문한 것으로 표시한다.
                if (maze[location[0] + direction.first][location[1] + direction.second] == 0 && !visit[location[0] + direction.first][location[1] + direction.second]) {
                    mazeQueue.add(intArrayOf(location[0] + direction.first, location[1] + direction.second))
                    visit[location[0] + direction.first][location[1] + direction.second] = true
                }
            }
        }
    }
}

// 벽은 X, 통로는 빈 문자, 현재 위치는 *로 표시하여 미로를 출력하는 함수.
fun printMaze(maze: List<List<Int>>, location: IntArray) {
    Array(maze.size) { i ->
        Array(maze[i].size) { j ->
            when {
                maze[i][j] == 0 -> "[ ]"
                else -> "[X]"
            }
        }
    }.apply {
        this[location[0]][location[1]] = "[*]"
    }.run {
        println("------------------")
        forEach { row ->
            row.forEach { cell ->
                print(cell)
            }.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][ ][ ]
------------------
------------------
[ ][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