Algorithm) DFS 알고리즘

Depth First Search

: 깊이 우선 탐색으로 다음 분기로 넘어가기 전에 한 분기를 끝까지 탐색한다.

• 특징)
  - 트리를 이용한 알고리즘
  - 순환 알고리즘이며 방문 여부를 검사하여 순환에서 빠져나간다.
  - 느리긴 하지만 완전 탐색이 가능하다.
  

Kotlin으로 구현해보자.

Node
: 각 분기점을 담당하며 정보를 가지고 있다.

	data class Node(
        val value: Int,
        val edge: MutableList<Node>
    ){
        var visited = false
    }

Main

	fun main() {
    	val node1 = Node(1)
        val node2 = Node(2)
        val node3 = Node(3)
        val node4 = Node(4)
        val node5 = Node(5)

        node1.edge.add(node2)
        node1.edge.add(node3)
        
        node2.edge.add(node4)
        node3.edge.add(node5)
    }

dfs 함수
탐색 함수를 정의해봅시다.

	fun dfs(node: Node) {
        println(node.value)
        node.edge.forEach {
            dfs(it)
        }
    }

dfs 결과 -> 1,2,4,3,5

---

하지만 Node를 무조건 정의해야하는 것은 아니다.

https://school.programmers.co.kr/learn/courses/30/lessons/87946

도전하다가 다른 블로그 풀이를 보았다.

fun solution(k: Int, dungeons: Array<IntArray>): Int {
        var maxCount = 0
        
        fun dfs(k: Int, dungeons: Array<IntArray>, visited: BooleanArray, count: Int) {
        maxCount = maxOf(maxCount, count)
        for (i in dungeons.indices) {
            val required = dungeons[i][0]
            val cost = dungeons[i][1]
            
            if (!visited[i] && k >= required) {
                visited[i] = true
                dfs(k - cost, dungeons, visited, count + 1)
                visited[i] = false
            }
        }
    }
        
        dfs(k, dungeons, BooleanArray(dungeons.size), 0)
        return maxCount
    }

node를 따로 만드는 것이 아니라 그때그때 변수들을 이용하였다.(훨씬 간단해이지만 문제를 풀때 떠올리긴 좀...)