728x90
이해하기
처음 시도했던 방식은 다음과 같다.
- 모든 경우의 수 탐색 : 순열 사용
- 던전 입장 가능 여부 확인
- 피로도 계산
import java.util.*;
class Solution {
List<int[]> list = new ArrayList<>();
public int solution(int k, int[][] dungeons) {
int[] order = {0, 1, 2};
permutation(order, 0, order.length, order.length);
int count = 0;
int max = 0;
for (int i = 0; i < list.size(); i++) {
int pirodo = k;
count = 0;
int[] cur = list.get(i);
for (int j = 0; j < cur.length; j++) {
int idx = cur[j];
if (pirodo >= dungeons[idx][0]) {
pirodo -= dungeons[idx][1];
count++;
}
}
max = Math.max(max, count);
if (max == dungeons.length) {
return max;
}
}
return max;
}
public void permutation(int[] order, int depth, int n, int r) {
if (depth == r) {
int[] temp = order.clone();
list.add(temp);
return;
}
for (int i = depth; i < n; i++) {
swap(order, depth, i);
permutation(order, depth + 1, n, r);
swap(order, depth, i);
}
}
public void swap(int[] order, int depth, int i) {
int temp = order[depth];
order[depth] = order[i];
order[i] = temp;
}
}
순열은 풀 때마다 어렵게만 느껴졌는데 아래 블로그를 참고해서 응용해보았다.
그렇지만 줄줄이 뜨는 실패...^^
시간초과도 아니고 그냥 실패라고만 떠서 뭐가 문제였는지 파악은 하지 못했다.
테스트 케이스는 통과한 것으로 보아 뭔가 로직이 꼬인 것 같은데🥹
도저히 모르겠어서 아래 블로그를 참고하였다.
이 문제는 백트래킹 dfs 문제였다네...
접근 방법은 다음과 같다.
- 이미 방문한 던전인지 확인
- visited 배열 이용
- 만약 visited = true라면 다음으로 넘어감
- 각 던전의 필요 피로도와 현재 피로도를 비교하며 탐험 여부 판단
- 방문한 적 없고, 현재 피로도 <= 필요 피로도라면 점화식 수행
- 해당 던전을 방문한 것으로 처리
- depth + 1과 현재 피로도에서 해당 던전의 소모 피로도만큼 감소한 상태로 다음 재귀
- 해당 던전을 방문하지 않은 것으로 처리 (백트래킹 때문?)
- 방문한 적 없고, 현재 피로도 <= 필요 피로도라면 점화식 수행
이 문제는 완전 탐색이기 때문에 점화식의 종료 조건은 따로 없다.
문제풀이
class Solution {
static boolean[] visited;
static int count = 0;
public int solution(int k, int[][] dungeons) {
visited = new boolean[dungeons.length];
dfs(0, k, dungeons);
return count;
}
public void dfs(int depth, int fatigue, int[][] dungeons) {
for (int i = 0; i < dungeons.length; i++) {
if (visited[i] || dungeons[i][0] > fatigue) {
continue;
}
visited[i] = true;
dfs(depth + 1, fatigue - dungeons[i][1], dungeons);
visited[i] = false;
}
count = Math.max(count, depth);
}
}
static boolean[] visited;
static int count = 0;
파라미터를 줄이기 위해 전역 변수로 visited 배열과 count를 선언한다.
public int solution(int k, int[][] dungeons) {
visited = new boolean[dungeons.length];
dfs(0, k, dungeons);
return count;
}
visited 배열을 dungeon 배열에 맞게 만들어주고, dfs를 돌린다.
public void dfs(int depth, int fatigue, int[][] dungeons) {
for (int i = 0; i < dungeons.length; i++) {
if (visited[i] || dungeons[i][0] > fatigue) {
continue;
}
던전을 순회하며, 만약 이미 방문했거나 필요 피로도가 현재 피로도보다 크다면 방문하지 못하고 넘어간다.
visited[i] = true;
dfs(depth + 1, fatigue - dungeons[i][1], dungeons);
visited[i] = false;
}
방문 가능하다면 visited[i]를 true로 변경해주고, 1 늘어난 depth와 줄어든 피로도로 다시 dfs를 돌린다.
백트래킹을 위해 visited[i]는 다시 false로 변경해준다.
count = Math.max(count, depth);
count는 Math.max로 계산한다.
생각보다 풀이는 쉬웠지만 역시 구현은 어렵다...ㅜㅅㅜ
bfs는 감 좀 잡았다고 생각했는데, dfs는 더 공부해야겠다.
'JAVA > Coding Test Study' 카테고리의 다른 글
[Lv.3] 네트워크 : Java (0) | 2024.03.26 |
---|---|
[Lv.2] 타겟 넘버 : Java (0) | 2024.03.26 |
[Lv.2] 쿼드압축 후 개수 세기 : Java (0) | 2024.03.22 |
[Lv.2] 무인도 여행 : Java (0) | 2024.03.20 |
[Lv.2] 게임 맵 최단거리 : Java (0) | 2024.03.20 |