[Java][백트래킹] 프로그래머스 Lv2_피로도

📌 개인적인 공간으로 공부를 기록하고 복습하기 위해 사용하는 블로그입니다.
정확하지 않은 정보가 있을 수 있으니 참고바랍니다 :😸
[틀린 내용은 댓글로 남겨주시면 복받으실거에요]

백트래킹

백트레킹 알고리즘이란?

• 가능성이 없는 곳에서는 되돌아가고 가능성이 있는 곳을 탐색하는 알고리즘
• 백트래킹으로 해가 될 가능성이 없는 탐색 대상을 배제할 수 있어서 완전탐색보다 효율적
• 문제마다 성능이 다르며, 시간 복잡도를 특정하기 어려움

백트래킹 중요 개념

1. 탐색: 가능한 모든 경우를 시도하면서 해를 찾기
2. 가지치기(Pruning): 해가 될 가능성이 없으면 그 경로는 더 이상 진행하지 않고 탐색을 종료
3. 재귀(Recursion): 함수가 자기 자신을 호출하면서 문제를 점진적으로 해결

유망함수

• 해가 될 가능성을 판단하는 것이 백트래킹 알고리즘의 핵심
• 해가 될 가능성 → 유망 함수로 정의하여 판단
• 유망하지 않은 경우는 가지치기(Pruning)하여 탐색을 중단
• 유망 함수 진행과정
  1. 유효한 해의 집합을 정의
  2. 위 단계에서 정의한 집합을 그래프로 표현
  3. 유망함수 정의
  4. 백트래킹 알고리즘 활용하여 해를 찾기

[예제] 프로그래머스 Lv2. 피로도 풀어보기

프로그래머스 Lv2. 피로도

문제분석

1. 현재 피로도가 최소 필요 피로도보다 낮으면 탐험 불가 → 백트래킹
2. 모든 던전을 탐험할 수 있는 경우의 수를 탐색하며, 최대로 탐험한 던전 수를 기록

문제 풀기

class Solution {
    private int answer;
    private boolean[] visited;
    private int[][] dg;
    
    public int solution(int k, int[][] dungeons) {
        answer = 0;
        dg = dungeons;
        
        visited = new boolean[dungeons.length];
        backtrack(k, 0);
        
        return answer;
    }
    
    //백트래킹
    private void backtrack(int k, int cnt) {
        for(int i = 0; i < dg.length; i ++) {
            //방문한적 없고,
            // 현재 피로도가 최소 필요피로도보다 크거나 같으면
            if(!visited[i] && k >= dg[i][0]) {
                visited[i] = true;
                // 소모 피로도를 반영하여 재귀 호출
                backtrack(k-dg[i][1], cnt +1);
                answer = Math.max(answer, cnt+1); // 최대 탐험 수 갱신
                visited[i] = false; // 방문 초기화 (백트래킹)
            }
        }
    }
}

탐색과정

• 초기 상태:

  시작 피로도 k = 80

  던전 리스트: [[80, 20], [50, 40], [30, 10]]

  방문 기록: visited = [false, false, false]

• 1단계: 첫 번째 던전 탐험

  현재 피로도 80은 던전 1의 최소 필요 피로도 80 이상이므로 탐험 가능

  탐험 후 소모 피로도 20을 빼서 남은 피로도는 60

  방문 기록: visited = [true, false, false]

• 2단계: 두 번째 던전 탐험

  남은 피로도 60은 던전 2의 최소 필요 피로도 50 이상이므로 탐험 가능

  탐험 후 소모 피로도 40을 빼서 남은 피로도는 20

  방문 기록: visited = [true, true, false]

• 3단계: 세 번째 던전 탐험 실패

  남은 피로도 20은 던전 3의 최소 필요 피로도 30보다 작으므로 탐험 불가

  → 백트래킹 발생! 두 번째 던전을 탐험하지 않았던 상태로 돌아감

• 4단계: 첫 번째 던전 이후 다른 선택 탐색

  다른 던전 순서를 탐험하면서 모든 경우를 확인

  • 던전 3 → 던전 2
  • 던전 2 → 던전 3 등

• 최종 결과: 탐험 가능한 던전 수가 최대값인 경우를 기록

Programmers 카테고리 내 다른 글 보러가기