[TIL/04.10] Algorithm: 백트래킹 (Java)

1. 문제

1부터 N까지 숫자 중 합이 10이 되는 조합 구하기 

 

입출력 예시

N	result
5	[[1,2,3,4], [1,4,5], [2,3,5]]

 

2. 코드

import java.util.*;

class Solution {
    private static ArrayList<ArrayList<Integer>> result;
    private static int n;
    
    private static void backtrack(int sum, ArrayList<Integer> selectedNums, int start){
        // 합이 10이 되면
        if (sum == 10){
            result.add(selectedNums);
            return;
        }
        
        for (int i = start; i <= n; i ++){
            if (sum +i <= 10){
                ArrayList<Integer> list = new ArrayList<>(selectedNums);
                list.add(i);
                backtrack(sum+i, list, i+1);
            }
        }
    }
    
    private static ArrayList<ArrayList<Integer>> solution(int N){
        result = new ArrayList<>();
        n = N;
        
        backtrack(0, new ArrayList<>(), 1);
        return result; 
        
    }
}

 

3. 체크 포인트

✅ 조합한 숫자 합이 10이 되면 해당 조합을 결과 리스트에 추가

✅ 조합한 숫자 합이 10보다 크면 백트래킹 

 

---

1. 문제

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

 

2. 코드

class Solution {
    private static int answer;
    private static int[][] Dungeons;
    private static boolean[] visited;
    
    private static void backtrack(int k, int cnt){
        for(int i = 0; i < Dungeons.length; i++){
            // 1. 현재 피로도(k)가 최소 필요 피로도보다 크거나 같고
            // 던전을 방문한 적이 없다면
            if (!visited[i] && k >= Dungeons[i][0]){
                visited[i] = true; // 방문 처리 
                // 2. 현재까지의 최대 탐험 가능 던전 수와
                // i번째 던전에서 이동할 수 있는 최대 탐험 가능 던전 수 중 큰 값을 선택해 업데이트
                backtrack(k - Dungeons[i][1], cnt + 1);
                answer = Math.max(answer, cnt +1);
                visited[i] = false; 
            }
            
        }

    }
    
    public int solution(int k, int[][] dungeons) {
        answer = 0;
        Dungeons = dungeons;
        visited = new boolean[dungeons.length];
        
        backtrack(k, 0); // dfs 수행 
        return answer;
    }
}

 

3. 체크 포인트

✅ 백트래킹을 할 때는 DFS의 끝단까지 탐색 후 이전노드로 돌아갈 때 방문 여부(check 배열)와 방문 횟수(cnt)를 이전 노드까지 탐색했을 때의 값으로 복구