프로그래머스 - 피로도

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

프로그래머스

 

보자마자 dfs 가 떠오른 문제다.

신경써야할 부분은 입장에 필요한 최소 피로도와 소모 피로도를 dfs 를 돌때

계속 업데이트 해주면서 방문체크와 함께 해주면 된다.

 

그리고 여러 순서로 던전을 방문하는걸 다 체크 해봐야하기 때문에

방문을 한 뒤에 로직이 끝날때는 방문처리를 해제해주자.

class Solution {
    var visited = booleanArrayOf()
    var answer: Int = -1
    lateinit var dungeon : Array<IntArray>
    fun solution(k: Int, dungeons: Array<IntArray>): Int {
         visited = BooleanArray(dungeons.size)
         dungeon = dungeons
         for(i in 0 until dungeons.size){
            if(!visited[i] && k >= dungeon[i][0]){
                 dfs(k -dungeon[i][1] ,i , 1)
            }
            visited[i] = false
         }
  
        return answer
    }
    
    fun dfs( current : Int, v : Int , count : Int){
        visited[v] = true
        answer = maxOf(answer , count)
        for(i in 0 until dungeon.size){
            if(!visited[i] && current >= dungeon[i][0]){    
                dfs(current - dungeon[i][1] , i , count+1 )    
            }
        }
        visited[v] = false
    }
}