문제 설명
XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다.
이때, 각 던전마다 탐험을 시작하기 위해 필요한 “최소 필요 피로도”와 던전 탐험을 마쳤을 때 소모되는 “소모 피로도”가 있습니다.
“최소 필요 피로도”는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, “소모 피로도”는 던전을 탐험한 후 소모되는 피로도를 나타냅니다.
예를 들어 “최소 필요 피로도”가 80, “소모 피로도”가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다.
유저의 현재 피로도 k와 각 던전별 “최소 필요 피로도”, “소모 피로도”가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.
제한사항
- k는 1 이상 5,000 이하인 자연수입니다.
- dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
- dungeons의 가로(열) 길이는 2 입니다.
- dungeons의 각 행은 각 던전의 [“최소 필요 피로도”, “소모 피로도”] 입니다.
- “최소 필요 피로도”는 항상 “소모 피로도”보다 크거나 같습니다.
- “최소 필요 피로도”와 “소모 피로도”는 1 이상 1,000 이하인 자연수입니다.
- 서로 다른 던전의 [“최소 필요 피로도”, “소모 피로도”]가 서로 같을 수 있습니다.
문제 이해
그러니까, 던전을 입장하기 위해서는 일정 피로도가 필요하고 (소모되는 건 아님)
던전을 끝내면 이때 일정 피로도가 소모가 됨
처음엔 엥 최소 필요 피로도가 80이고, 소모 피로도가 20이면 총 100의 피로도가 필요한 거 아닌가
생각을 했는데, 최소 필요 피로도는 들어갈 때 최소한 이만큼은 있어야 한다고 정해준 거고
던전을 다 돌았을 때만 소모 피로도가 깎이는 구조임.
그럼 어떻게 풀어야하나
1. 현재 피로도로 갈 수 있는 던전들을 찾아본다.
2. 그 중 하나를 선택해서 탐험한다.
3. 소모 피로도만큼 피로도를 감소시킨다.
4. 아직 방문하지 않은 던전 중 다시 갈 수 있는 곳을 찾아본다.
근데 모든 경우의 수를 다 탐색해서, 던전을 가장 많이 돌 수 있는 횟수를 알아내야 한다.
dfs가 적절해보인다.
1차 코드
package programmers.P87946;
public class Main {
static int[][] d = {{80, 20}, {50, 40}, {30, 10}};
static boolean[] visited;
static int maxCount;
public static void main(String[] args) {
int k = 80;
System.out.println(solution(k));
}
public static int solution(int k) {
int n = d.length;
visited = new boolean[n];
maxCount = Integer.MIN_VALUE;
dfs(k, 0);
return maxCount;
}
public static void dfs(int k, int cnt) {
if (cnt > maxCount) {
maxCount = cnt;
}
for (int i = 0; i < d.length; i++) {
if (visited[i]) {
continue;
} else {
if (k >= d[i][0]) {
visited[i] = true;
dfs(k - d[i][1], cnt + 1);
visited[i] = false;
} else {
continue;
}
}
}
}
}
넘 지저분하고 가독성이 떨어진다고 생각돼서 리팩토링 + 제출용 코드로 수정하겠다.
2차 코드
package programmers.P87946;
public class Main {
static boolean[] visited;
static int maxCount;
public static int solution(int k, int[][] dungeons) {
int n = dungeons.length;
visited = new boolean[n];
maxCount = 0;
dfs(dungeons, k, 0);
return maxCount;
}
public static void dfs(int[][] dungeons, int k, int cnt) {
maxCount = Math.max(maxCount, cnt);
for (int i = 0; i < dungeons.length; i++) {
if (visited[i]) {
continue;
}
if (k < dungeons[i][0]) {
continue;
}
visited[i] = true;
dfs(dungeons, k - dungeons[i][1], cnt + 1);
visited[i] = false;
}
}
}
풀이
1. `visited`라는 `boolean` 타입의 공통 필드를 만들어 각 던전의 방문 여부를 관리
2. 최대 방문 횟수를 저장할 `maxCount`를 `0`으로 초기화
(처음에는 `Integer.MIN_VALUE`를 넣으려고 했지만, 방문할 수 있는 던전이 하나도 없는 경우에도 정답은 `0`이므로 `0`으로 초기화했다.)
3. `visited`를 던전 개수만큼의 `boolean` 배열로 초기화
4. `dfs(dungeons, k, 0)`을 호출하여 탐색
이때 `k`는 현재 피로도, `0`은 현재까지 방문한 던전의 개수임
5. `DFS`가 호출될 때마다 현재 방문한 던전 수 `cnt`와 `maxCount`를 비교하여 더 큰 값을 `maxCount`에 저장한다.
6. `[A, B, C]`라는 던전이 있다면
`A → ...`, `B → ...`, `C → ...`처럼 시작하는 던전과 방문 순서에 따라 결과가 달라질 수 있으므로, 반복문을 사용해 방문 가능한 모든 던전을 확인
7. 이미 방문한 던전이라면 `continue`
8. 현재 피로도가 해당 던전의 최소 필요 피로도보다 작다면 입장할 수 없으므로 `continue`
9. 입장할 수 있는 던전이라면 `visited[i] = true`로 방문 처리
10. 현재 피로도에서 해당 던전의 소모 피로도를 빼고, 방문한 던전 수 `cnt`를 1 증가시킨 상태로 다시 `DFS`를 호출
11. 해당 경로의 탐색이 끝나고 이전 상태로 돌아오면 `visited[i] = false`로 방문 취소 (백트래킹)
간단한 dfs문제였다.