[프로그래머스 , kotlin] 피로도

 

 

연결리스트를 이용한 풀이 ( 스택과 같은 기능으로)

fun solution_ff(k: Int, dungeons: Array<IntArray>): Int {


    val stack = mutableListOf(Triple(k, 0, BooleanArray(dungeons.size)))
    var maxCount = 0

    while (stack.isNotEmpty()) {
        val (currentK, count, visited) = stack.removeAt(stack.lastIndex)
        maxCount = maxOf(maxCount, count)

        for (i in dungeons.indices) {
            if (!visited[i] && currentK >= dungeons[i][0]) {
                val newVisited = visited.copyOf()
                newVisited[i] = true
                stack.add(Triple(currentK - dungeons[i][1], count + 1, newVisited))
            }
        }
    }

    return maxCount



}

DFS 스택을 사용한 탐색 시나리오

1. 초기 상태: 피로도: 80, 탐험한 던전 수: 0, 방문 상태: [false, false, false]
2. 첫 번째 스택 상태: 스택: [(80, 0, [false, false, false])]
3. 첫 번째 상태에서 가능한 던전 탐험:
   • 던전 0 탐험 가능:
     피로도: 60, 탐험한 던전 수: 1, 방문 상태: [true, false, false]

     스택: [(60, 1, [true, false, false])]
   • 던전 1 탐험 가능:
     피로도: 40, 탐험한 던전 수: 1, 방문 상태: [false, true, false]

     스택: [(60, 1, [true, false, false]), (40, 1, [false, true, false])]
   • 던전 2 탐험 가능:
     피로도: 70, 탐험한 던전 수: 1, 방문 상태: [false, false, true]

     스택: [(60, 1, [true, false, false]), (40, 1, [false, true, false]), (70, 1, [false, false, true])]
4. 스택에서 다음 상태를 꺼내고 탐험을 진행합니다. 예를 들어 (60, 1, [true, false, false]) 상태를 탐험하면:
   • 던전 1 탐험 가능:
     피로도: 20, 탐험한 던전 수: 2, 방문 상태: [true, true, false]

     스택: [(40, 1, [false, true, false]), (70, 1, [false, false, true]), (20, 2, [true, true, false])]
   • 던전 2 탐험 가능:
     피로도: 50, 탐험한 던전 수: 2, 방문 상태: [true, false, true]

     스택: [(40, 1, [false, true, false]), (70, 1, [false, false, true]), (20, 2, [true, true, false]), (50, 2, [true, false, true])]
5. 이 과정을 반복하여 모든 가능한 상태를 탐색합니다.
6. 최종적으로 최대 탐험 가능한 던전 수는 3이 됩니다.

 

재귀를 이용한 풀이 

fun solution(k: Int, dungeons: Array<IntArray>): Int {
    var maxCount = 0

    fun dfs(remainingK: Int, count: Int, visited: BooleanArray) {
        maxCount = maxOf(maxCount, count)

        for (i in dungeons.indices) {
            if (!visited[i] && remainingK >= dungeons[i][0]) {// 방문하지 않은 던전이면서 입장이 가능한지 확인합니다.

                visited[i] = true // 방문 처리 후 
                dfs(remainingK - dungeons[i][1], count + 1, visited)
                visited[i] = false
            }
        }
    }

    dfs(k, 0, BooleanArray(dungeons.size))
    return maxCount
}

재귀를 사용한 DFS 탐색 시나리오

1. 초기 상태:  피로도: 80, 탐험한 던전 수: 0, 방문 상태: [false, false, false]
2. 첫 번째 재귀 호출: dfs(80, 0, [false, false, false])
3. 첫 번째 던전(80, 20) 탐험 가능:
   • 상태 갱신 후 재귀 호출:
   • 피로도: 60, 탐험한 던전 수: 1, 방문 상태: [true, false, false] dfs(60, 1, [true, false, false])
4. 두 번째 던전(50, 40) 탐험 가능:
   • 상태 갱신 후 재귀 호출:
     피로도: 20, 탐험한 던전 수: 2, 방문 상태: [true, true, false] dfs(20, 2, [true, true, false])
   • 피로도가 부족하여 세 번째 던전 탐험 불가, 돌아감.
5. 두 번째 던전 탐험이 끝난 후 세 번째 던전(30, 10) 탐험 가능:
   • 상태 갱신 후 재귀 호출:
     피로도: 50, 탐험한 던전 수: 2, 방문 상태: [true, false, true] dfs(50, 2, [true, false, true])
   • 두 번째 던전 탐험 가능:
     피로도: 10, 탐험한 던전 수: 3, 방문 상태: [true, true, true] dfs(10, 3, [true, true, true])
6. 두 번째 던전 탐험이 끝난 후 상태 복구:
   • 상태 복구 후 세 번째 던전 탐험:
     피로도: 60, 탐험한 던전 수: 1, 방문 상태: [true, false, false] dfs(60, 1, [true, false, false])
7. 두 번째 던전(50, 40) 탐험 가능:
   • 상태 갱신 후 재귀 호출:
     피로도: 20, 탐험한 던전 수: 2, 방문 상태: [false, true, false] dfs(20, 2, [false, true, false])
8. 세 번째 던전(30, 10) 탐험 가능:
   • 상태 갱신 후 재귀 호출:
     피로도: 10, 탐험한 던전 수: 3, 방문 상태: [false, true, true] dfs(10, 3, [false, true, true])
9. 상태 복구 후 세 번째 던전 탐험:
   피로도: 70, 탐험한 던전 수: 1, 방문 상태: [false, false, true] dfs(70, 1, [false, false, true])
10. 두 번째 던전(50, 40) 탐험 가능:
    • 상태 갱신 후 재귀 호출:
      피로도: 30, 탐험한 던전 수: 2, 방문 상태: [false, true, true] dfs(30, 2, [false, true, true])
11. 첫 번째 던전(80, 20) 탐험 가능:
    • 상태 갱신 후 재귀 호출:
      피로도: 10, 탐험한 던전 수: 3, 방문 상태: [true, true, true] dfs(10, 3, [true, true, true])

최종적으로 최대 탐험 가능한 던전 수는 3이 됩니다.