[프로그래머스] 피로도 (Swift)

https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=swift

프로그래머스

완전탐색 (DFS)

N개의 던전을 탐색하는 문제인데, k만큼의 체력을 갖고 있을 때, 각 던전에 들어갈 때 필요한 체력과, 각 던전을 들어갔을 때 실제로 사용되는 체력이 주어지고, 최대한 많은 던전을 탐색할 수 있는 경우를 구하는 문제

탐색 순서가 달라질 수 있다는 게 문제다

 

접근방법

dfs 재귀 방식으로 풀었는데, 종료조건을 어떻게 두어야 할지 고민했다. 

그래서 처음에는 모든 던전을 실제로 들어갔거나, 더이상 들어갈 수 있는 던전이 없을 때를 확인했는데,

따로 확인할 필요는 없었다..cnt는 실제로 들어간 던전의 갯수니까 커질때마다 갱신해주면 되고,

더이상 방문할 수 없을 경우 for문에서 알아서 아무것도 못하고 재귀함수 호출도 못하고 나올 것임

순서가 상관있는 문제여서 재귀함수 안에서 매번 모든 던전을 탐색하면서 갈 수 있는지, 확인하고, 갈 수 있다면 간다.

이 부분이 헷갈린 포인트였던 것 같다. 보통은 갈 수 있을 때, 가는 경우와 가지 않는 경우의 dfs 호출을 따로따로 해주는데,

이번에는 방문여부를 체크하지 않기 때문에 매번 모든 노드를 확인해서, 첫번째 반복때 0번 노드를 갔다면, 두번째 반복때는 0번노드를 가지 않는 경우에 대한 연산을 하게 되는 거다 (으..알아듣게 썼나 모르겠다) 백트래킹..?같다는 생각도 했다

 

 

소스코드

import Foundation

var answer = 0

func dfs(_ k:Int, _ cnt:Int, _ visit:[Bool], _ dungeons:[[Int]]) {
    if answer < cnt {
        answer = cnt
    }

    for i in 0..<dungeons.count {
        var needK = dungeons[i][0]
        var useK = dungeons[i][1]
        if k >= needK && !visit[i] {
            var _visit = visit
            _visit[i] = true
            dfs(k-useK, cnt+1, _visit, dungeons)
        }
    }
    
    return
}

func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    
    var visit = Array<Bool>(repeating: false, count: dungeons.count)
    dfs(k, 0, visit, dungeons)
    
    return answer
}