완전탐색
프로그래머스 레벨2 피로도 문제이다.
이 문제를 풀면서 dfs의 동작 방식에 대해 좀 더 잘 이해할 수 있었던것 같다.
풀이
- 각 던전의 인덱스에 해당하는 방문 기록 visited를 만든다.
- for 문을 돌려서 인덱스에 해당하는 던전에 방문하지 않았고, 입장 시 필요한 피로도를 충족한 경우를 찾는다.
- 방문 기록을 남기고 다음 depth로 깊이 우선 탐색을 실행한다.
- for 문의 다음 루프에 영향이 가지 않도록 visited 를 초기화 한다.
- 재귀함수를 돌아서 가장 깊은 depth 까지 탐색을 한 경우의 depth를 기록한다.
최종 코드
import java.util.*;
class Solution {
static int answer = 0;
static boolean[] visited;
public void dfs(int[][] dungeons, int left, int depth) {
// 2. for 문을 돌려서 인덱스에 해당하는 던전에 방문하지 않았고,
// 입장 시 필요한 피로도를 충족한 경우를 찾는다.
for (int i = 0; i < dungeons.length; i++) {
if (visited[i] == false && left >= dungeons[i][0]) {
// 3. 방문 기록을 남기고 다음 depth로 깊이 우선 탐색을 실행한다.
visited[i] = true;
dfs(dungeons, left - dungeons[i][1], depth +1);
// 4. for 문의 다음 루프에 영향이 가지 않도록 visited 를 초기화 한다.
visited[i] = false;
}
}
// 5. 재귀함수를 돌아서 가장 깊은 depth 까지 탐색을 한 경우의 depth를 기록한다.
answer = Math.max(answer, depth);
}
public int solution(int k, int[][] dungeons) {
// 1. 각 던전의 인덱스에 해당하는 방문 기록 visited를 만든다.
visited = new boolean[dungeons.length];
int left = k;
dfs(dungeons, left, 0);
return answer;
}
}'알고리즘 > 완전탐색' 카테고리의 다른 글
| [알고리즘] 소수찾기 (0) | 2023.11.12 |
|---|