[프로그래머스 / Java] 코딩테스트 연습: 피로도 (완전탐색)

난이도: Level 2

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

프로그래머스

---

 

dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.

만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면 .... (생략)

만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면 .... (생략)

=> 데이터의 수 N이 8밖에 안되고, 모든 순서를 탐색해야 하므로 백트래킹으로 풀면 된다.

 

우선 Solution 클래스의 인스턴스 변수로 최종 리턴할 answer 변수와 던전을 방문 체크할 visited 배열을 선언한다.

여기에 선언하는 이유는 dfs 메서드에서 이 변수들을 사용할 것이기 때문이다.

dfs 메서드의 매개변수에는 k, 2차원 dungeons 배열, depth, count를 넘겨준다.

k: 유저의 현재 피로도 (문제의 매개변수로 주어짐)

dungeons: 2차원 던전 배열 (문제의 매개변수로 주어짐)

depth: 호출할 dfs 메서드 깊이 => 0부터 시작

count: 탐색할 던전 수 => 0부터 시작

그리고 dfs 메서드를 마치고 유저가 탐험할 수 있는 최대 던전 수 answer를 리턴해준다.

 

    class Solution {

        int answer = 0;     // 유저가 탐험할 수 있는 최대 던전 수

        boolean[] visited;  // 던전 방문 체크 배열

           

        public int solution(int k, int[][] dungeons) {

            visited = new boolean[dungeons.length];  // 던전의 수 만큼 크기 초기화

            // 모든 탐색 순서를 구하는 dfs 시작

            // k: 유저의 현재 피로도 (k)

            // depth: 호출할 dfs 메서드 깊이 (0)

            // count: 탐색한 던전 수 (0)

            dfs(k, dungeons, 0, 0);    

            return answer;  // 유저가 탐험할 수 있는 최대 던전 수 리턴

        }

 

 

dfs 메서드는 다음과 같다.

dfs 메서드 깊이(depth)가 던전 수(dungeons.length)와 같다면 던전을 모두 방문했다는 뜻이다.

 

참고로 여기서 방문, 탐색, 탐험은 다른 뜻이다.

방문: 던전 탐험 조건(유저의 현재 피로도가 던전의 최소 피로도 이상)과 상관없이 무조건 체크

탐색: 던전 탐험 조건(유저의 현재 피로도가 던전의 최소 피로도 이상)과 상관없이 무조건 체크

탐험: 던전 탐험 조건(유저의 현재 피로도가 던전의 최소 피로도 이상)을 만족하면 체크

 

유저가 탐험한 던전 수(count)가 현재 설정된 answer보다 크다면 answer는 count로 바뀐다.

이런 식으로 유저가 탐험할 수 있는 최대 던전 수를 갱신해준다.

그리고 또다른 탐색 순서를 찾으러 가기 위해 dfs 메서드를 종료시킨다.

 

 

dfs 메서드 깊이(depth)가 던전 수(dungeons.length)와 같지 않다면 아직 모든 던전을 다 방문하지 않았으므로, 아래에 있는 for문으로 던전들을 탐색한다.

현재 던전(i번째 던전)을 방문하지 않았다면 방문 체크를 해준다.

 

유저의 현재 피로도 k가 i번째 던전의 최소 피로도 dungeons[i][0] 이상이라면 던전을 탐험할 수 있다는 뜻이므로, dfs 매개변수를 다음과 같이 설정한다.

k: 유저의 현재 피로도에서 i번째 던전의 소모 피로도만큼 빼기 (k - dungeons[i][1])

dungeons: 배열을 그대로 넘겨줌 (dungeons)
depth: 호출할 dfs 메서드 깊이 1 증가 (depth + 1)
count: 탐색한 던전 수 1 증가 (count + 1)

 

유저의 현재 피로도 k가 i번째 던전의 최소 피로도 dungeons[i][0]보다 작다면 이라면 던전을 탐험할 수 없다는 뜻이므로, dfs 매개변수를 다음과 같이 설정한다.

k: 유저의 현재 피로도 그대로 유지 (k)

dungeons: 배열을 그대로 넘겨줌 (dungeons)
depth: 호출할 dfs 메서드 깊이 1 증가 (depth + 1)
count: 탐색한 던전 수 그대로 유지 (count)

 

dfs 메서드가 끝나면 현재 던전(i번째 던전)의 방문 체크를 해제해준다.

탐색 후 방문 체크를 해제해주어야 던전의 탐색 순서 경우의 수를 모두 찾을 수 있다. 

 

    public void dfs(int k, int[][] dungeons, int depth, int count) {

        // dfs 메서드 깊이(depth)가 던전 수(dungeons.length)와 같다면 던전 탐색 종료

        if (depth == dungeons.length) {

            // 유저가 탐험한 던전 수(count)가 현재 answer보다 크다면

            // 유저가 탐험할 수 있는 최대 던전 수(answer)가 변경됨

            answer = Math.max(answer, count);

            return;     // 또다른 탐색 순서 찾으러 가기

        }

       

        // 모든 던전 탐색

        for (int i = 0; i < dungeons.length; i++) {

            if (!visited[i]) {  // i번째 던전을 방문하지 않았다면

                visited[i] = true;  // i번째 던전 방문 체크

               

                // 유저의 현재 피로도(k)가 던전의 최소 피로도(dungeons[i][0]) 이상이라면 던전 탐험 가능

                if (k >= dungeons[i][0]) {

                    // k: 유저의 현재 피로도에서 던전의 소모 피로도만큼 빼기 (k - dungeons[i][1])

                    // depth: 호출할 dfs 메서드 깊이 1 증가 (depth + 1)

                    // count: 탐험한 던전 수 1 증가 (count + 1)

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

                } else {    // 그렇지 않다면 던전 탐험 불가

                    // k: 유저의 현재 피로도 그대로 유지 (k)

                    // depth: 호출할 dfs 메서드 깊이 1 증가 (depth + 1)

                    // count: 탐험한 던전 수 그대로 유지 (count)

                    dfs(k, dungeons, depth + 1, count);

                }

               

                visited[i] = false;     // i번째 던전 방문 체크 해제

            }

        }

    }

 

---

전체 코드

class Solution {
    int answer = 0;     // 유저가 탐험할 수 있는 최대 던전 수
    boolean[] visited;  // 던전 방문 체크 배열
        
    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];  // 던전의 수 만큼 크기 초기화
        // 모든 탐색 순서를 구하는 dfs 시작
        // k: 유저의 현재 피로도 (k)
        // depth: 호출할 dfs 메서드 깊이 (0)
        // count: 탐색한 던전 수 (0)
        dfs(k, dungeons, 0, 0);     
        return answer;  // 유저가 탐험할 수 있는 최대 던전 수 리턴
    }
    
    public void dfs(int k, int[][] dungeons, int depth, int count) {
        // dfs 메서드 깊이(depth)가 던전 수(dungeons.length)와 같다면 던전 탐색 종료
        if (depth == dungeons.length) {
            // 유저가 탐험한 던전 수(count)가 현재 answer보다 크다면
            // 유저가 탐험할 수 있는 최대 던전 수(answer)가 변경됨
            answer = Math.max(answer, count); 
            return;     // 또다른 탐색 순서 찾으러 가기
        }
        
        // 모든 던전 탐색
        for (int i = 0; i < dungeons.length; i++) {
            if (!visited[i]) {  // i번째 던전을 방문하지 않았다면
                visited[i] = true;  // i번째 던전 방문 체크
                
                // 유저의 현재 피로도(k)가 던전의 최소 피로도(dungeons[i][0]) 이상이라면 던전 탐색 가능
                if (k >= dungeons[i][0]) {
                    // k: 유저의 현재 피로도에서 던전의 소모 피로도만큼 빼기 (k - dungeons[i][1])
                    // depth: 호출할 dfs 메서드 깊이 1 증가 (depth + 1)
                    // count: 탐색한 던전 수 1 증가 (count + 1)
                    dfs(k - dungeons[i][1], dungeons, depth + 1, count + 1);
                } else {    // 그렇지 않다면 던전 탐색 불가
                    // k: 유저의 현재 피로도 그대로 유지 (k)
                    // depth: 호출할 dfs 메서드 깊이 1 증가 (depth + 1)
                    // count: 탐색한 던전 수 그대로 유지 (count)
                    dfs(k, dungeons, depth + 1, count);
                }
                
                visited[i] = false;     // i번째 던전 방문 체크 해제
            }
        }
    }
}