문제 링크

바로가기

문제 풀이

JS

function solution(k, dungeons) {
    let answer = Number.MIN_SAFE_INTEGER;
    const visited = new Array(dungeons.length).fill(false);
    
    const dfs = (health, dungeons, cnt) => {
        answer = Math.max(answer, cnt);
        
        for(let i = 0; i < dungeons.length; ++i) {
            if (health < dungeons[i][0] || health - dungeons[i][1] < 0 || visited[i]) continue;
            visited[i] = true;
            dfs(health - dungeons[i][1], dungeons, cnt + 1);
            visited[i] = false;
        }
    }
    
    dfs(k, dungeons, 0);
    return answer;
}

PY

import sys

def solution(k, dungeons):
    answer = -sys.maxsize
    visited = [False for _ in range(len(dungeons))]
    
    def dfs(health, dungeons, cnt):
        nonlocal answer
        answer = max(answer, cnt)
        
        for idx, dungeon in enumerate(dungeons):
            if(visited[idx] or health < dungeons[idx][0] or health - dungeons[idx][1] < 0):
                continue
            visited[idx] = True
            dfs(health - dungeons[idx][1], dungeons, cnt + 1)
            visited[idx] = False
    
    dfs(k, dungeons, 0)
    return answer

풀이

DFS의 정석인 문제

모든 경우의 수를 탐색해야하고 범위가 크지 않을 때 DFS 고려해봐야한다.
재귀함수를 통해 문제를 해결했는데 방문 체크를 하는 것과 동시에 조건에 맞으면 재귀한다.

새롭게 배운 점

1. 파이썬에서 함수 내부에서 전역 변수를 수정하려고 하면 nonlocal 키워드가 필요하다.