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

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

프로그래머스

---

class Solution {
    static boolean[] visited;
    static int n = 0;
    
	static int solution(int k, int[][] dungeons) {
        int answer = -1;
        
        int dunLen = dungeons.length;
        visited = new boolean[dunLen];
        
        backtracking(k, 0, dunLen, dungeons);
        
        answer = n;
        return answer;
    }
	
    // 백트래킹 함수 (dfs 활용)
	public static void backtracking(int energy, int depth, int dunLen, int[][] dungeons) {
        if(depth > n) n = depth;
		if(depth == dunLen) return;
    	
    	for(int i = 0 ; i < dunLen ; i++) {
    		if(!visited[i]) {
    			if(energy >= dungeons[i][0]) {
                    visited[i] = true;
    				backtracking(energy - dungeons[i][1], depth + 1, dunLen,  dungeons);
                    // 방문 초기화
        			visited[i] = false;
    			}
    		}
    	}
    }
}

 

백트래킹을 이용하여 문제를 해결했습니다.

 

backtracking 함수를 재귀호출 할 때에 energy -= dungeons[i][0] 을 하게 되면 다른 분기에서 계산할 때 이전에 계산된 energy의 값이 영향을 미칠 수 있기 때문에 backtracking(energy - dungeons[i][1], depth + 1, dunLen); 으로 써야한다는 것을 주의해야 합니다.

 

---

백트래킹을 잘 모르시는 분들은 관련 문제 N과 M을 참고하셔서 차근히 개념알아가시면 될 것 같습니다.

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

(제출한 코드가 아니라서 입력형식은 생략했습니다.)

// BackTracking
// 백트래킹을 DFS로 구현함

public class N과M {
	static int[] arr;
	static boolean[] visited;
	public static void main(String[] args) {
		int N = 4, M = 2;
		visited = new boolean[N];
		arr = new int[M];
		
		backtracking(N, M, 0);
		
	}
	
	static void backtracking(int N, int M, int depth) {
		// 한 가지(분기)의 끝
		if(depth == M) {
			for(int i = 0 ; i < M ; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			return;
		}
		
		for(int i = 0 ; i < N ; i++) {
			// 방문했는지 체크
			if(!visited[i]) {
				visited[i] = true;
				arr[depth] = i + 1;
				// depth + 1
				backtracking(N, M, depth + 1);
				// visited 복구
				visited[i] = false;
			}
		}
	}
}

 

백트래킹 알고리즘 특성 상 가지치기로 내려가다가 조건과 다르면 다시 올라가야하므로 visited를 이용합니다. depth를 이용해 깊이를 압니다. 첫 노드부터 시작되므로 지나온 노드의 개수와 depth는 같습니다. 만약 노드의 개수가 전체 노드와 같다면 한 분기의 모든 탐색을 끝낸 것이므로 return 합니다.