2020-12-30

DFS(Depth-First Search)

미로를 탐색하는 방법의 일종이다. DFS는 스택이나 재귀 함수를 이용하는데, 방문한 위치에서 진행 가능한 한 방향으로 계속 이동한 후에 더 이상 진행할 수 없다면 뒤로 돌아가면서 방문하지 않은 다른 방향으로 다시 깊게 탐색한다.
written by

스택 또는 재귀 함수를 이용한 미로 탐색 알고리즘

미로를 탐색하는 방법의 일종이다. DFS는 스택이나 재귀 함수를 이용하는데, 방문한 위치에서 진행 가능한 한 방향으로 계속 이동한 후에 더 이상 진행할 수 없다면 뒤로 돌아가면서 방문하지 않은 다른 방향으로 다시 깊게 탐색한다. 그래서 큐를 이용하지 않고 FILO(First In, Last Out)인 스택을 이용한다. 이렇게 하면 분기점에서 한 방향으로 끝까지 탐색한 후에 목적지가 없다면 분기점으로 돌아가는 게 아니라 가장 가까운 방문하지 않은 이전 노드로 가게 된다.

DFS는 목적지를 찾더라도 최단 경로임을 보장하지는 않는다. 한쪽으로 깊게만 탐색하기 때문이다. 최단 경로를 알기 위해서는 결국 모든 노드를 방문해서 비용을 비교해야 한다.

Algorithm

시작 지점에서 DFS 함수를 호출한다. 방문 여부를 귀납 조건으로 설정해 준다. 동서남북의 이동 가능한 위치로부터 DFS 함수를 호출한다. 이렇게 하면 이동이 불가능할 때까지 한 방향으로 방문을 계속하게 된다. 아래의 결과를 보면 알겠지만, FILO(First In, Last Out)인 스택을 이용하는 방법이므로 BFS와는 방문 순서가 반대인 것을 알 수 있다.

Kotlin Code

// 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 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),
)

// DFS 탐색 시작
dfsSearch(intArrayOf(0, 0))

fun dfsSearch (currentPosition: IntArray) {

    // 귀납 조건(Base Case).
    // 귀납 조건은 맨 위에 설정하는 것이 쓸데없는 작업을 줄여주므로 좋다.
    // 이미 방문한 곳이라면 재귀를 탈출하도록 설정.
    if (visit[currentPosition[0]][currentPosition[1]]) return

    // 귀납 조건 다음에 귀납 조건을 만족하도록 설정.
    // 현재 위치를 방문한 것을 표시할 수 있으므로, 적절함.
    visit[currentPosition[0]][currentPosition[1]] = true

    // 현재 맵을 프린트.
    printMap(map, currentPosition)

    // 도착 지점이라면 Search Success 출력.
    if(currentPosition.contentEquals(goalPosition)) {
        println("Search Success")
    }

    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]) {
                dfsSearch(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][ ][*]
--------------------
Search Success
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][*][X][ ][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][*][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][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