그래프 탐색 - 깊이우선 탐색 (DFS Depth-First Search) feat.kotlin

정의

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

그래프에서는 탐색을 시작하는 노드를 시작으로 인접한 노드로 지속적으로 이동한다. 

더 이상 탐색을 하지 않은 인접한 노드가 없을 때 까지 탐색을 진행후, 부모노드로 돌아와서 탐색하지 않은 인접한 노드를 탐색한다.

인접한 모든 노드가 탐색이 완료되면 종료한다.

 

* 탐색은 한번 방문한 노드는 다시 방문하지 않습니다. (부모노드로 돌아오는것 이외에)

 

 

* 현재 노드에서 다음 노드로 이동시 인접한 노드중에 선택하는 기준은 위 그림에선 왼쪽 --> 오른쪽이다.

 

V - 정점(노드)의 개수

E - 간선의 개수 

 

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

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

 

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

시간복잡도 O(V^2)

 

완전탐색 및 백트레킹에 많이 쓰임.

깊이 탐색할때, 인접한 노드중에 탐색 순서의 기준도 중요함.

특정 조건의 여부에 따라 탐색을 중단하는것에 유용함.

재귀함수를 이용한 구현

// 그래프 탐색 DFS

private val vNum = 6
val adj = Array(vNum) { mutableListOf<Int>() }
val visited = Array(vNum) { 0 }

fun dfs(g: Array<MutableList<Int>>, v: Int) {
    println("v: $v")
    visited[v] = 1
    for (nv in adj[v]) {
        if (visited[nv] == 1) continue
        dfs(g, nv)
    }
}

fun draw(){
    adj[1].add(2)
    adj[1].add(4)

    adj[2].add(1)
    adj[2].add(3)

    adj[3].add(2)
    adj[3].add(5)

    adj[4].add(1)
    adj[5].add(3)
}

fun main() {
    draw()
    dfs(adj, 1)
    println(visited.joinToString())
}

 

/*
 맵(2차원 배열) 탐색 DFS
 맵의 특정 위치는 y(row) x(col)로 좌표로 나타낸다.
 Pair<Int, Int> 또는 2개의 Int Type 파라미터를 필요로 한다.
 아래 코드는 맵을 탐색하면서 연결된 덩어리 지역을 방문을 표기한다.
 
 nxn 의 정사각의 맵이 주어졌다면,
 
 V = n*n개
 E = (n-1)(2n)개

 시간 복잡도는
  O(n^2 + 2n^2 - 2n)
  --> O(n^2)
*/

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

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

val rows = 5
val cols = 5
val visited = Array(rows) { IntArray(cols) { 0 } }

fun mDfs(map: Array<IntArray>, p: Pair<Int, Int>) {

    visited[p.first][p.second] = 1

    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 (map[ny][nx] == 1 && visited[ny][nx] != 1) {
            mDfs(map, ny to nx)
        }
    }
}

fun main() {

    var connectedComponentCnt = 0

    for (i in 0 until rows) {
        for (j in 0 until cols) {
            if (map[i][j] == 1 && visited[i][j] != 1) {
                connectedComponentCnt += 1
                mDfs(map, i to j)
            }
        }
    }

    visited.forEach { println(it.joinToString()) }
    println(connectedComponentCnt)
}