24.02.15

프로그래머스 피로도 문제 풀다가 도저히 내 지식으로는 풀 수 없다...

이건 그냥 모든 경우의 수를 다 돌아보고? 그중 가장 좋은 케이스를 가져와야 하는데.... 이거 모든 케이스를 어떻게 돌려야 하지???? 한 한시간 들여다보다가 도저히 모르겠어서 답지 봄!

 

[완전 탐색]

• 가능한 모든 경우의 수를 다 시도해 답을 찾는 방법
• 정확하고 확실하게 답을 찾을 수는 있지만, 시간이 오래 걸린다.
• 모든 경우의 수를 구하는 문제 같은 부분에서 많이 사용되는 알고리즘
• 조합, 중복 조합, 순열, 중복 순열
• 1부터 n까지의 수를 모두 더하기
• 난수에서 배열에서 특정한 수 찾기 등

기본적으로 스택과 큐로 구현을 하게 되는데, 이를 재귀 함수로 표현할 수 있음.

class Solution {
    public int answer; // 최대 던전 수
    public boolean[] visited; // 방문 여부

    public int solution(int k, int[][] dungeons) {
        // dungeons 배열의 길이만큼 방문 여부 배열 선언
        visited = new boolean[dungeons.length];

        // dfs 메서드 호출
        dfs(0, k, dungeons);

        // 결과 반환
        return answer;
    }

    public void dfs(int depth, int k, int[][] dungeons) {
        for (int i = 0; i < dungeons.length; i++) {
            // 방문하지 않은 상태면서 k가 최소 필요 피로도보다 크거나 같은 경우
            if (!visited[i] && dungeons[i][0] <= k) {
                visited[i] = true; // 방문 처리
                dfs(depth + 1, k - dungeons[i][1], dungeons); // 재귀 호출
                visited[i] = false; // 방문 초기화
            }
        }
        
        answer = Math.max(answer, depth);
    }
}

함수 안에 자기를 호출하는 재귀 함수로 표현됨.

아직 이게 완전히 이해되진 않는다. 

코드를 한번 이해보자.

배열 길이만큼 반복을 시켜. 그다음음에? 방문했는지 체크를 하고, K가 피로도보다 크거나 같애? 그럼 로직에 들어가. 방문처리해주고? 다시 시작해 어떻게? 깊이를 하나 더 늘려서

이때는 이미 갔던 길은 방문처리기ㅏ 됐겠지?