프로그래머스 - 피로도

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

프로그래머스

 

dfs를 연습해볼 수 있는 좋은 문제인 것 같다.

 

이 문제에서 dfs를 사용해야하는 이유는 다음과 같다.

1. 던전을 순차적으로 방문할 필요는 없다.
2. 모든 경우를 구하여 최대 방문 횟수를 구해야 한다.

때문에 dfs를 구현하여 가능한 모든 경우의 수에서 최대 던전 탐험 횟수를 구하면 된다.

 

<코드>

import java.util.*;
class Solution {
    public static int count=0;
    public static boolean[] visited;
    public int solution(int k, int[][] dungeons) {
        int answer = -1;
        visited=new boolean[dungeons.length];
        dfs(k,dungeons,0);
        answer=count;
        return answer;
    }
    
    public void dfs(int k, int[][] dungeons, int clear){
        count=Math.max(clear,count);
        
        for(int i=0; i<dungeons.length; i++){
            if(!visited[i]){
                if(k>=dungeons[i][0]){
                    visited[i]=true;
                    dfs(k-dungeons[i][1],dungeons,clear+1);
                    visited[i]=false;
                }
            }
        }
    }
}

 

위 코드가 배열을 순차적으로 방문하는 경우 외에도 역순이나 다른 모든 순회를 구할 수 있는 이유

 

방문 후 visit를 false로 변경하여 다음 재귀에서 이전 던전도 방문하는 경우를 구할 수 있도록 한다.

 

 

• 첫 번째 루프 (i = 0):
  • 던전 0을 탐험.
  • 재귀 호출에서 남은 던전 [50, 40], [30, 10]에 대해 탐험을 진행.
• 재귀 호출 후 복구:
  • visited[0] = false로 돌아갑니다.
  • 이제 던전 1부터 탐험을 시도.
• 두 번째 루프 (i = 1):
  • 던전 1을 탐험.
  • 재귀 호출에서 남은 던전 [80, 20], [30, 10]에 대해 탐험.
• 마지막 루프 (i = 2):
  • 던전 2를 탐험.
  • 재귀 호출에서 남은 던전 [80, 20], [50, 40]에 대해 탐험.

 

따라서 모든 던전 순회의 경우를 구한다.

• 0 → 1 → 2
• 0 → 2 → 1
• 1 → 0 → 2
• 1 → 2 → 0
• 2 → 0 → 1
• 2 → 1 → 0

 

---

2025년 03월 21일

 

 

<오류 코드>

import java.util.*;

class Solution {
    static boolean[] visit;
    static int answer = -1;
    public int solution(int k, int[][] dungeons) {
        visit = new boolean[dungeons.length];
        dfs(k,dungeons,0);
        
        return answer;
    }
    
    public void dfs(int k, int[][] dungeons, int count){
        
        for(int i=0; i<dungeons.length; i++){
            if(!visit[i]){
                if(k>=dungeons[i][0]){
                    visit[i]=true;
                    k-=dungeons[i][1];
                    count+=1;
                    answer=Math.max(count,answer);
                    dfs(k,dungeons,count);
                    count-=1;
                    visit[i]=false;
                }
            }
            
        }
    }
}

 

왜 오류가 생겼을까?

 

재귀 호출에서 k값을 빼주면 다시 더해줘서 다음 반복문에 영향을 안 가도록 해줘야하는데 k값을 원상복구 안시켜줘서 정상적으로 작동하지 않았다.

 

 

정답코드

import java.util.*;

class Solution {
    static boolean[] visit;
    static int answer = -1;
    public int solution(int k, int[][] dungeons) {
        visit = new boolean[dungeons.length];
        dfs(k,dungeons,0);
        
        return answer;
    }
    
    public void dfs(int k, int[][] dungeons, int count){
        
        for(int i=0; i<dungeons.length; i++){
            if(!visit[i]){
                if(k>=dungeons[i][0]){
                    visit[i]=true;
                    k-=dungeons[i][1];
                    count+=1;
                    answer=Math.max(count,answer);
                    dfs(k,dungeons,count);
                    count-=1;
                    k+=dungeons[i][1];
                    visit[i]=false;
                }
            }
            
        }
    }
}