[프로그래머스/Java] 피로도

문제

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

문제풀이 방법

<백트랙킹 기법 사용>
백트랙킹이란? 완전탐색기법으로 DFS와 달리 불필요한 부분은 가지치기를 하여
지금의 경로가 맞지 않다고 파악이 되면 더 이상 나아가지 않고 돌아옴 유망성 판단

1. 방문하지 않았고 dungeons[i][0]가 k보다 작거나 같을 때 
	-> visited[i] 방문 처리
	-> 재귀로 다시 backtrack 함수로 보냄 k = k - dangeons[i][1] (첫번째 던전에서 피로도 소모)
	-> cnt ++
	 
2. cnt와 answer을 비교해 cnt가 더 크면 answer = cnt (최댓값으로 answer 갱신)

나의 코드

class Solution {
    int answer = 0;
    boolean[] visited;
    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        backtrack(k, 0, dungeons);
        return answer;
    }
	    public void backtrack(int k, int cnt, int[][] dungeons){
	        if(answer < cnt)
	            answer = cnt; // answer의 최댓값 갱신
	        for(int i = 0; i < dungeons.length; i++){
	            if(!visited[i] && dungeons[i][0] <= k){
	                visited[i] = true;
	                backtrack(k - dungeons[i][1], cnt + 1, dungeons);
	                visited[i] = false; //백트래킹 기법: 원래 상태로 되돌려놓기 
	            }
	        }
    }
}