[알고리즘 문제풀이] 프로그래머스 - 피로도

➕ 오늘 푼 문제

프로그래머스 - 피로도

➕ 아이디어

• dungeon 함수에서 방문할 수 있는 모든 던전의 경우의 수를 다 따져 최대값을 구한다.
  • k: 현재 피로도
  • now: 남은 던전 목록
  • count: 지금까지 방문한 던전 수
• 재귀 함수(dungeon)의 로직
  • 남은 던전 목록을 순회하며 방문 가능한 던전을 뽑는다.
  • 해당 던전을 방문하고 다시 dungeon 을 호출한다.

➕ Java 코드

import java.util.*;

class Solution {
    public int dungeon(int k, List<List<Integer>> now, int count){
        int result = count;
        
        for(int i=0; i<now.size(); i++){
            int m = now.get(i).get(0);
            int c = now.get(i).get(1);
            
            if(k >= m){
                List<List<Integer>> next = new ArrayList<>();
                next.addAll(now.subList(0, i));
                next.addAll(now.subList(i+1, now.size()));
                
                result = Math.max(result, dungeon(k-c, next, count+1));
            }
        }
        return result;
    }
    
    public List<List<Integer>> convertIntList(int[][] dungeons){
        List<List<Integer>> result = new ArrayList<>();
        
        for(int i=0; i<dungeons.length; i++){
            List<Integer> temp = new ArrayList<>();
            for(int j=0; j<dungeons[i].length; j++){
                temp.add(dungeons[i][j]);
            }
            result.add(temp);
        }
        
        return result;
    }
    
    public int solution(int k, int[][] dungeons) {
        List<List<Integer>> dungeonList = convertIntList(dungeons);
        return dungeon(k, dungeonList, 0);
    }
}

[참고] dfs 버전

import java.util.*;

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

➕ Python 코드

def dungeon(k, now, count):
    result = count
    for i in range(len(now)):
        m, c = now[i]
        if k >= m:
            next = now[:i] + now[i+1:]
            result = max(dungeon(k-c, next, count+1), result)
    return result

def solution(k, dungeons):
    return dungeon(k, dungeons, 0)

➕ 궁금한 내용 및 소감

• 사실 내가 생각한 아이디어를 조금만 더 바꾸면 dfs로도 구현할 수 있다고 한다. 방문 여부를 체크하는 배열을 따로 둬서 재귀 형태로 구현하면 된다.
• 자바의 경우 dfs로 구현하는 게 서브 리스트 처리를 하는 것보다 구현이 쉬워 코드를 추가해놓았다. 파이썬은 리스트를 분리하고 합치는 게 상대적으로 자유로워서 지금처럼 구현해도 좋을 것 같다.

➕ 참고 문헌

• Java
  • 참고 링크: 2차원 Array, List로 변경하기
  • 침고 링크: Java - 두개의 List를 하나로 합치는 방법