2020-12-22

깊이 우선 탐색(DFS, Depth-First Search)

DFS(Depth-First Search)는 스택을 이용한 방법과 재귀적인 방법으로 구현한다. 여기서는 스택을 이용한 방법으로 문제를 해결하려고 한다.
written by

Introduction

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

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

  • 정해진 방향으로 가면서 분기 지점에서 갈 수 있는 모든 지점들을 후보로 기록한다.
  • 길이 막히면 되돌아가면서 아직 가지 않은 다음 후보 지점으로 간다.

이런 방법으로 가다 보면 길이 막힐 때 아직 가지 않은 가장 가까운 후보 지점으로 돌아가서 길이 막힐 때까지 미로를 탐색하게 되고, 결국 도착 지점까지 가는 길이 있다면 도착 지점에 도착할 것이다. 이 방식이 DFS(Depth-First Search)의 원리이다. 길이 막힐 때까지 가본 후에 되돌아와서 안 가본 길을 가보는 것은 가장 사람다운 길 찾기 방식이라고 할 수 있다.

이 방식의 단점은 찾은 경로가 최단 경로임을 보장하지는 않는다는 점이다. 가는 경로가 여러 개 있어도 제일 긴 경로로 먼저 길을 알아냈을 수도 있기 때문이다.

Algorithm

DFS(Depth-First Search)는 스택을 이용한 방법과 재귀적인 방법으로 구현한다.

여기서는 스택을 이용한 방법으로 문제를 해결하려고 한다. 두 가지 방식의 차이점은 방문 순서이다. 재귀적인 방식은 가장 먼저 확인한 지점으로 이동하지만, 스택을 이용한 방식은 가장 나중에 확인한 지점으로 이동한다. 이제 미로를 탈출해보자. 우선 시작 지점을 스택에 넣고 방문한 것으로 표시한다.

  • 방문할 수 있는 모든 후보 지점을 스택에 푸시 하고 방문한 것으로 표시한다.
  • 스택의 탑을 현재 위치로 옮겨 준 후에 팝 한다.
  • 방문한 곳은 건너뛰고 위의 과정을 경로를 발견할 때까지 반복한다.

후보 지점이 겹치는 경우도 있으므로 후보 지점을 확인한 시점에 방문한 것으로 표시해서 중복으로 방문하지 않도록 한다. 이제 길이 막혀서 스택이 더 쌓이지 않는다면 여태까지 방문한 지점은 건너뛰고 가장 가까운 후보 지점으로 이동해서 목적 지점을 향해 계속 경로를 탐색할 것이다.

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 mazeStack = ArrayDeque<IntArray>().apply { push(location) }

// 스택이 다 비어도 도착 지점을 찾지 못하면 경로가 없다.
while (mazeStack.isNotEmpty()) {

    // 스택에서 탐색 중인 위치를 현재 위치로 저장하고 스택에서 팝 한다.
    location[0] = mazeStack.element()[0]
    location[1] = mazeStack.element()[1]
    mazeStack.pop()

    // 미로를 출력한다.
    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]) {
                    mazeStack.push(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][ ][*]
------------------
2021 © Cinntiq's Studio