https://school.programmers.co.kr/learn/courses/30/lessons/87946
문제 접근
k : 주어진 내 피로도
dungueons[[최소 피로도 , 소모 피로도 ]]
result : 가장 많은 던전을 탐험하는 방법
(80,20) : A, (50,40) : B, (30,10) : C라고 해보자
그러면 시스템에서 생각해볼 수 있는 최대 경우의 수는 6가지 일 것이다.
모든 케이스를 확인하고 탐색해봐야하니까.. DFS라고 할 수 있겠다.
많이 나오는 DFS의 기본적인 형태를 오늘은 좀 정리해보고자 한다.
dfs 마스터하고싶다...
DFS 사용 예시
모든 가능한 조합(경우의 수)을 탐색하면서,
조건을 만족하는 경우를 세거나, 최대/최소값을 갱신한다.
DFS 접근 단계별 정리
① dfs 함수에서 매개변수로 관리할 값 정하기
쉽게 말해, 현재 단계에서 알아야 하는 정보들을 관리하는 것이다.
이 문제를 예시로 들어서 생각해보자!
만약 내가 A라면 지금 내가 어디를 갈까? 그리고 거기를 갈 수 있는 피로도인가?
그리고 지금 몇개의 던전을 거쳐왔지?여기서
- 지금 내가 어디를 갈 수 있을지, 지금 내가 어디인지 → 방문한 상태 (visited[])
- 거기를 갈 수 있는 피로도인가? → 현재 피로도 (k)
- 지금 몇 개의 던전을 거쳐왔지? → 탐험한 개수 (count)
② 종료 조건 생각하기
언제 이 재귀를 멈출지 생각하는 단계이다.
탐험한 개수가 주어진 배열의 길이와 같거나,
현재 가진 피로도가 다음 최소 필요 피로도보다 작다면 더 이상 탐험할 수 없다.즉, 더 진행할 수 없는 시점에서 종료하고 결과를 갱신한다.
③ 탐색 로직 설계 (for문 + 조건문)
언제 재귀를 호출할 것인지, 그 조건이 무엇인지를 설계하는 단계이다.
for문을 돌면서
- i번째 던전을 아직 방문하지 않았고
- 최소 필요 피로도 ≤ 현재 피로도(k)
위 조건을 만족하면 방문 처리를 한 뒤에
dfs()를 호출해 다음 탐색을 진행한다.
④ 백트래킹 (상태 복구)
매우 중요한 단계.
탐색이 끝나면 다시 방문 상태를 되돌려야 한다.
그래야 다른 경로의 조합도 탐색할 수 있다.이 부분은 직관적으로 잘 안 와닿을 수 있으니 예시로 보자
A, B, C 세 노드가 있다고 가정해봅시다.
모두 처음에는 방문하지 않은 상태이므로
visited = [false, false, false]입니다.이제 A → B → C 순으로 DFS를 수행한다고 하면,
- A를 방문하면
visited[A] = true- 이어서 B를 방문하면
visited[B] = true- 다음으로 C를 방문하여 경로 A→B→C 탐색이 끝납니다.
이 시점에서 B의 방문 상태를 그대로(true) 둔다면,
다음 탐색인 A→C→B를 시도할 때
if (!visited[B])조건에 걸려서 B를 방문할 수 없게 됩니다.즉, 이전 탐색 경로(A→B→C)가 끝난 후에는
B의 방문 상태를 다시 false로 되돌려야 (A→C→B 탐색 가능)
다른 모든 가능한 조합(경로)을 탐색할 수 있게 됩니다.이것이 백트래킹(상태 복구)의 핵심이며,
“현재 노드(B)에 대한 탐색이 끝났다면,
그 노드의 방문 상태를 원래대로 되돌리는 것”이
DFS의 완전탐색을 보장합니다.
💡
DFS 호출 전후로 상태를 명확히 바꾸고 복구하기
→ “들어가기 전에 변경, 나오면서 되돌림”종료 조건을 함수 상단에 둬라
→ 예외 처리 실수를 줄이고 구조가 깔끔해진다
예시 코드
class Solution {
static int answer;
static boolean[] visited;
public int solution(int k, int[][] dungeons) {
answer = 0;
visited = new boolean[dungeons.length];
dfs(k, dungeons, 0);
return answer;
}
private void dfs(int k, int[][] dungeons, int count) {
// 정답 갱신
answer = Math.max(answer, count);
// 모든 노드(던전) 탐색
for (int i = 0; i < dungeons.length; i++) {
int min = dungeons[i][0]; // 최소 필요 피로도
int cost = dungeons[i][1]; // 소모 피로도
// 아직 방문 안했고, 탐험 가능할 때
if (!visited[i] && k >= min) {
visited[i] = true; // 방문 처리
dfs(k - cost, dungeons, count + 1); // 다음 탐색
visited[i] = false; // 백트래킹 (상태 복구)
}
}
}
}