출처: 프로그래머스 코딩 테스트 연습

문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한 사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  • dungeons의 가로(열) 길이는 2 입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

입출력 예

k	dungeons	result
80	[[80,20],[50,40],[30,10]]	3

입출력 예 설명

현재 피로도는 80입니다.

만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
• 남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.

만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
• 남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

내가 제출한 코드

import Foundation

var maxValue: Int = 0

func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    var visited = Array(repeating: false, count: dungeons.count)
    dfs(dungeons, k, 0, &visited)
    return maxValue
}

func dfs(_ data: [[Int]], _ pirodo: Int, _ level: Int, _ visited: inout [Bool]){
    for i in 0..<data.count {
        if !visited[i] && pirodo >= data[i][0] {
            visited[i] = true
            dfs(data,pirodo - data[i][1], level+1, &visited)
            maxValue = max(maxValue, level+1)
            visited[i] = false
        }
    }
}

코드 설명

이번 풀이는 완벽탐색을 이용한다. 처음에는 그리디로 접근을 시도했으나 접근법이 떠오르지 않아, 입력의 수 dungeons의 행 길이(던전의 수)가 8이하인 것을 보고 완벽탐색으로 접근을 시도하였다. 완벽탐색의 방법에도 반복문, 순열, 등이 있지만 해당 코드에서는 dfs(깊이우선탐색)을 사용한다.

그러면 코드를 세부적으로 살펴본다.

func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    var visited = Array(repeating: false, count: dungeons.count)
    dfs(dungeons, k, 0, &visited)
    return maxValue
}

우선 깊이우선탐색을 수행하기 위해 Bool배열을 선언한다. 이는 중복 탐색을 방지하기 위해 선언한다. 그리고 깊이우선탐색을 하는 함수 dfs을 살펴보자.

func dfs(_ data: [[Int]], _ pirodo: Int, _ level: Int, _ visited: inout [Bool]){
    for i in 0..<data.count {
        if !visited[i] && pirodo >= data[i][0] {
            visited[i] = true
            dfs(data,pirodo - data[i][1], level+1, &visited)
            maxValue = max(maxValue, level+1)
            visited[i] = false
        }
    }
}

data 파라미터에는 던전의 정보가 담겨있다. pirodo프로퍼티에는 현재 피로도의 정보, level은 탐험한 던전의 수를 가지게 된다. 함수 내부에 반복문이 실행되는 것을 알 수 있다. 이는 모든 경우의 수를 탐색하기 위해서 사용한다. 이때 ([80,20] -> [80,20])와 같이 똑같은 곳을 방문하는 것을 방지하기 위해 visited프로퍼티를 true로 할당한다. 이는 현재 i 번째 던전(노드)를 방문하였단 의미이다. 방문 체크를 한 뒤 다음 던전을 탐색하기 위해 dfs(data, pirodo - data[i][1], level+1, &visited)를 호출한다.

만약 다음 던전을 돌고 더 이상 방문할 수 있는 던전이 없다면 visited[i] = false의 코드로 실행의 흐름이 이동한다. 이는 해당 방문 경로(경우의 수)를 탐색했으니 다른 경로의 탐색을 위해 필요한 코드이다. 이를 반복할 경우 던전을 완전탐색할 수 있다.

최대 던전 수는 어떻게 알 수 있을까? level프로퍼티의 값으로 확인할 수 있다. 제일 처음 level프로퍼티의 값은 0이다. 이는 현재 방문한 던전의 수가 0이라는 뜻이다. 다음, 조건문 if ! visited[i] && pirodo >= data[i][0]을 만족하면 다음 던전을 탐색하므로 level+1을 수행한다. 이는 던전을 1개 방문할 것이라는 의미가 된다. 그러므로 maxValue = max(maxValue, level+1)을 통해 최대 방문 던전의 수를 계속해서 업데이트하게 된다. 마지막으로 maxValue값을 반환하면 문제를 해결할 수 있다.