[프로그래머스] (Java) 피로도 (완전탐색)

📑 1. 문제설명

 

---

💡 2. 나의 코드 

문제에서 구해야 하는 것 - 최대 몇 번 던전을 돌 수 있는지 횟수

 

즉, 존재하는 던전들을로 도는 순서 바꿔가면서 가능한 모든 조합을 만든다.

만약 A,B,C 던전이 있다면? `A-B-C`,`A-C-B`,`B-A-C`,`B-C-A`, `C-A-B`, `C-B-A` 조합을 모두 순회하면서

최대로 몇 번 돌 수 있는지 카운팅 해 준다.

 

백트래킹과 DFS(깊이 우선 탐색)

백트래킹과 dfs로 모든 경우의 수를 조합 해 준다.

depth 는 탐색횟수이다.

구하는 순간 answer = Math.max(answer, depth) 해서 최댓값 업데이트

class Solution {
    // 전역 변수 선언
    public static int answer; // 최대 던전 탐험 횟수
    public static boolean[] visited; // 각 던전의 방문 여부
        
    // 문제 답 반환하는 메서드
    public int solution(int k, int[][] dungeons) {
        answer= 0; // 초기값 설정
        visited = new boolean[dungeons.length]; // 방문 여부 배열 초기화
        
        // 백트래킹 탐색 시작
        // (현재 탐험 깊이 0, 초기 피로도 k, 던전 정보 전달)
        backTracking(0, k, dungeons);
        return answer;
    }
        
    // 백트래킹 메서드: 가능한 모든 던전 탐험 경로를 탐색
    public static void backTracking(int depth, int k, int[][] dungeons) {
        // 던전 목록 순회
        for (int i = 0; i < dungeons.length; i++) {
            
            // 조건 1: 아직 방문하지 않은 던전
            // 조건 2: 현재 피로도(k)가 해당 던전 탐험 최소 요구 피로도(dungeons[i][0]) 이상
            if (!visited[i] && dungeons[i][0] <= k) {
                visited[i] = true; // 해당 던전을 방문 표시
                
                // 재귀 호출: 현재 던전을 탐험한 상태로 탐색 계속
                backTracking(depth + 1, k - dungeons[i][1], dungeons);
                
                // 백트래킹: 탐험을 되돌려 다음 경로를 탐색할 수 있도록 초기화
                visited[i] = false;
            }
        }
        // 현재까지의 탐험 깊이를 최대값으로 갱신
        answer = Math.max(answer, depth);  
    }
}

 

1) 백트래킹(Back Tracking)

1. 조건 :`if (!visited[i] && dungeons[i][0] <= k)` 

if문으로 방문하지 않은 던전 & 최소 필요 소모도 <= 현재 필요도 인 경우 if 문 내부 로직을 타게 된다. 
if문 타면 던전을 방문한 것으로 가정하므로, visited는 true가 된다.
현재 피로도(k)가 던전의 요구 피로도(dungeons[i][0])보다 작으면 해당 경로를 탐색하지 않고 되돌아간다.

조건을 만족하지 않는 경우 탐색하지 않음으로써 가지치기를 수행해 주는 것이다.

2. 다음 백트래킹을 태울 때는 depth는 +1 을 한다.

depth는 방문한 던전의 개수가가 되고, 초기값은 depth 0으로 시작한다.

현재 피로도 - 던전의 피로도만큼 차감시켜서 던전 방문 후 남은 피로도를 계산해서 현재 피로도를 업데이트 해 준다. 
 
더이상 if 내부 로직을 탈 수 없다(탐험불가) => 

여기서 백트래킹이 일어나는데 백트래킹은 곧 이전 상태로 복귀 (던전 1 탐험 취소)한다는 뜻이다. 

visited[i] = false로 초기화하여 탐색 상태를 되돌립니다.

이 과정은 다른 경로 탐색을 위해 초기화 해주는 백트래킹의 핵심이다. 
즉, backTracking(1, 60, dungeons) 상태로 복귀한다. 
그리고 for 루프에서 다음 던전 탐색 시작을 해 주는 것이다. 

던전 A,B,C 가 있다면 A-B-C, A-C-B 를 탐색 해 준 다음 B를 선두로 탐색을 할텐데,

A의 visited를 false로 해줘야지 처음과 같은 조건에서 B에서도 B-A-C, B-C-A 로 던전을 돌 수 있기 때문이다.

 

2) DFS(깊이 우선 탐색)

backTracking(depth + 1, k - dungeons[i][1], dungeons);

 

이 코드가 DFS의 핵심

 

backTracking 메서드는 이름은 백트래킹으로 지었지만

깊이 우선 탐색(DFS) 방식으로 한 경로를 끝까지 탐색한 후, 다른 경로를 탐색한다. 
for 루프를 통해 던전을 하나씩 탐색 => 재귀 호출로 다음 경로를 탐험한다.

 

DFS는 더 이상 탐험할 수 있는 던전이 없을 때 종료가 된다.

즉, 3개의 던전 중 조건에 맞는 던전이 없거나, 이미 탐색 가능한 모든 던전을 재귀 호출로 처리했다면

현재 호출된 backTracking 메서드의 for 루프가 종료가 되는 것이다.

이 시점에서 탐험한 던전 수(depth)가 현재까지의 최대값인지 확인하고,

`answer = Math.max(answer, depth);` 이후 상위 호출로 되돌아간다.
상위 호출은 백트래킹으로 이전 탐험 상태로 되돌아가며 다른 경로를 탐색하는 과정으로 계속 진행이 된다. 

 

⭐ DFS와 백트래킹 구분

조건 없이 모든 경로를 탐색: DFS
조건을 통해 탐색을 중단하고 가지치기: 백트래킹
결론적으로, `이 코드는 백트래킹이 포함된 DFS`라고 이해하면 됩니다......

---

👏🏻 3. 좋아요 제일 많이 받은 코드

class Solution {
    public static boolean check[];
    public static int ans = 0;

    public int solution(int k, int[][] dungeons) {
        check = new boolean[dungeons.length];

        dfs(k, dungeons, 0);

        return ans;
    }
    public static void dfs(int tired, int[][] dungeons, int cnt){
        for(int i=0; i<dungeons.length; i++){
            if(!check[i] && dungeons[i][0]<=tired){
                check[i] = true;
                dfs(tired-dungeons[i][1], dungeons, cnt+1);
                check[i] = false;
            }
        }
        ans = Math.max(ans, cnt);
    }
}

 

---

👉🏻 4. 같은 유형 문제