Lv.2- 피로도
1. 문제 요구사항
- 입력: 현재 피로도
k, 던전별 [최소 필요 피로도, 소모 피로도]가 담긴 2차원 배열dungeons. - 조건:
- 던전을 탐험하기 위해서는 '최소 필요 피로도' 이상이 남아있어야 한다.
- 탐험 후에는 '소모 피로도'만큼 차감된다.
- 하루에 탐험할 수 있는 최대 던전 수를 구해야 한다.
- 제한사항: 던전의 개수는 1 이상 8 이하다.
2. 접근 방식 (Algorithm)
1) 왜 그리디(Greedy)가 아닌가?
처음에는 효율적으로 풀기 위해 정렬을 고민했다. 하지만 "필요 피로도는 높고, 소모 피로도는 낮은" 던전이 무조건 최적의 선택이 아닐 수 있다.
예를 들어, 당장 소모가 적은 던전을 갔다가 남은 피로도가 애매하게 줄어들어, 이후에 갈 수 있는 다른 큰 던전들을 못 가게 될 수도 있기 때문이다.
2) 완전 탐색 (DFS) 선택 이유
문제의 제한사항을 보면 던전의 개수가 최대 8개밖에 되지 않는다.
최악의 경우 모든 순서를 다 따져봐도 가지밖에 되지 않으므로, 컴퓨터 연산 속도로는 순식간에 끝난다.
따라서 복잡한 그리디나 DP보다는, 재귀 함수를 이용해 모든 던전 방문 순서를 찔러보는(DFS) 방식이 가장 확실하고 구현하기 쉽다.
3) 로직 설계
visited배열: 이미 방문한 던전을 다시 가지 않도록 체크한다.- DFS 재귀 호출:
- 남은 던전 중 '방문하지 않았고' & '현재 피로도로 갈 수 있는' 던전을 찾는다.
- 방문 체크(
visited[i] = true) 후 재귀 호출한다. - 백트래킹: 재귀가 끝나고 돌아오면 다시 방문 체크를 해제(
visited[i] = false)하여 다른 순서를 탐색할 수 있게 한다.
- 최적화 (
stop플래그): 만약 현재 탐색 깊이(depth)가 전체 던전 개수와 같다면, 이미 최대치를 찾은 것이므로 더 이상 탐색하지 않고 종료한다.
import java.util.*;
class Solution {
int answer = 0;
boolean stop = false;
public int solution(int k, int[][] dungeons) {
boolean[] visit = new boolean[dungeons.length];
dfs(k, dungeons, visit, 0);
return answer;
}
public void dfs(int k, int[][] dungeons, boolean[] visit, int depth) {
if(stop) return;
if(depth == dungeons.length) {
stop = true;
return;
}
else {
for(int i=0; i<dungeons.length; i++){
if(visit[i]) continue;
if(k < dungeons[i][0]) {
continue;
}
visit[i] = true;
answer = Math.max(answer, depth+1);
dfs(k-dungeons[i][1], dungeons, visit, depth+1);
visit[i] = false;
}
}
}
}4. 느낀점 & 배운점
-
문제의 규모(N)를 먼저 보자던전 개수가 8개라는 아주 작은 숫자를 보고 바로 완전 탐색을 떠올렸어야 했다. 앞으로는 어떤 알고리즘을 쓸지 고민될 때 제한사항의 N 크기를 먼저 확인하는 습관을 들여야겠다. (이면 거의 무조건 완전 탐색이다.)
-
그리디의 함정
"당장 좋아 보이는 것"을 선택하는 그리디 방식은 반례가 존재할 가능성이 높다. 특히 이번 문제처럼 두 가지 조건(필요 피로도, 소모 피로도)이 서로 얽혀 있을 때는 더더욱 그렇다. 확실하지 않으면 완전 탐색이 정답이다. -
코딩 테스트에서의 static 주의
처음에는 answer와 stop을 static 변수로 선언했었는데, 프로그래머스 채점 환경에서는 여러 테스트 케이스가 하나의 클래스 인스턴스에서 실행될 수 있어 값이 누적되는 문제가 생길 수 있다는 점을 알았다. 멤버 변수로 선언하고 solution 내부에서 초기화해주는 것이 안전하다.
