던전을 탐험할 수 있는 "최소 필요 피로도", 던전을 탐험하고 난 후 소모되는 "소모 피로도"가 주어질 때, 최대한 많은 던전을 탐험할 수 있는 개수를 반환해야 한다.
문제를 해결하는 결론부터 말하면 그냥 모든 경우를 탐색하는 완전 탐색을 돌려서 문제를 해결해야 한다...
그러면 완전 탐색을 써야한다는 조건을 어떻게 알 수 있는데? 라고 물어보면 dungeons가 1이상 8이하로 최대 던전의 개수가 매우 작다.
그러니까 던전의 최대 8개 있다고 해도 8! 개수 만큼 수형도(트리 형태로 가지치기 하기)를 그리면 사실 문제를 해결할 순 있다는 뜻이 되고, 이를 코드로 구현하는 방법을 찾으라는 뜻이다.
이를 코드로 표현하기 위해서는 백트래킹이라는 기법을 이용해서 문제를 해결한다.
백트래킹? 이라고 하면 아마 다들 아래와 같이 개념을 떠올리곤 한다.
해를 찾는 도중에 막히면(해가 아니면) 되돌아가서 다시 해를 찾는 기법 아니야?
맞다. 맞긴 한데 이건 단순히 백트래킹 이라는 용어를 그대로 해석한 것 뿐이고, 실제로 코드로 어떻게 구현되는 지 알아야 문제를 해결할 수 있다.
백트래킹을 구하는 핵심 코드는 for문(반복문) + DFS + visited(방문배열) 이용이다!
아래 DFS 메서드를 생각해보자.
static void DFS(뭔진 모르지만 문제 조건에 따라 넘겨줄 매개변수들) {
for (int i = 0; i < 뭔진 또 모르지만 매개변수에 맞는 배열, 리스트, 컬렉션 개수만큼 순회; i++) {
if (!visited[i]) { // 아직 방문하지 않은 정점이라면
visited[i] = true;
DFS(depth가 1 증가했다는 표식을 함께 넘겨서 재귀호출);
visited[i] = false;
}
}
}우리가 아는 일반적인 DFS 메서드는 다음과 같다.
static void DFS(int v) {
visited[v] = true;
System.out.print(v + " ");
for (int i : A[v]) {
if (!visited[i]) {
DFS(i);
}
}
}둘의 차이가 보이는가? 눈에 띄는 건 visited 방문 배열의 체크 위치이다.
일반 DFS와 달리 백트래킹은 반복문 안에서 방문 표시를 남긴 뒤 재귀 호출이 끝나면 다시 방문 체크를 해제하여 원래 상태로 되돌리는 트릭을 사용한다.
반면 일반 DFS는 방문 표시를 메서드 호출 처음부터 설정한 뒤 다시 되돌리는 과정이 없다.
이를 잘 활용하여 던전을 탐험하는 문제를 풀면 다음과 같다.
class Solution {
static int max;
public int solution(int k, int[][] dungeons) {
max = -1;
boolean[] visited = new boolean[8];
DFS(k, 0, dungeons, visited);
return max;
}
public static void DFS(int k, int count, int[][] dungeons, boolean[] visited) {
for (int i = 0; i < dungeons.length; i++) {
if (!visited[i] && k >= dungeons[i][0]) {
visited[i] = true;
DFS(k - dungeons[i][1], count + 1, dungeons, visited);
visited[i] = false;
}
}
max = Math.max(max, count);
}
}방문 여부 조건문에 최소 푈요 피로도가 k를 넘으면 던전을 탐험할 수 없으므로 해당 내용을 추가한다.
DFS가 계속 재귀적으로 호출되다가 더 들어갈 수 있는 던전이 없으면 재귀가 끝난다.
바로 이 시점에서 max = Math.max(max, count); 코드 위치에 도달하게 되고, 그 시점의 count로 max값을 갱신하는 것이다.
예시 데이터인 k = 80, dungeons = [[80,20],[50,40],[30,10]], result = 3으로 생각해보자.
1) DFS(80, 0, dungeons, visited)
i = 0
visited[0] = true
DFS(80 - 20, 0 + 1, dungeons, visited); // 재귀 호출 1
2) DFS(60, 1, dungeons, visited)
i = 0
visited[0] = true 이므로 skip
i = 1
visited[1] = true
DFS(60 - 40, 1 + 1, dungeons, visited) // 재귀 호출 2
3) DFS(20, 2, dungeons, visited)
i = 0, i = 1 visited = true 이므로 skip
i = 2
if (!visited[2] && 20 >= 30) 이므로 false
따라서 더 이상 DFS를 실행하지 않고 재귀 호출 종료!!
이 시점에서 max = Math.max(max, count);이 실행됨
따라서 아래와 같이 호출되었던 재귀 함수가 아래와 같이 호출되며 반환됨
1) DFS(20, 2, dungeons, visited): max = Math.max(0, 2) = 2
2) DFS(60, 1, dungeons, visited): max = Math.max(2, 1) = 2
여기서 아직 DFS(80, 0, dungeons, visited)은 반복문을 진행하고 있는 중이다!
따라서 첫 번째 다음으로 세 번째 던전을 선택하는 DFS(50, 2, dungeons, visited)로 이동하게 된다.
따라서 전체 탐색 그림은 다음과 같다.
DFS(80, 0)
└─ 0번 선택 → DFS(60, 1)
├─ 1번 선택 → DFS(20, 2)
│ └─ 더 이상 못 감 → max = 2
│
└─ 2번 선택 → DFS(50, 2)
└─ 1번 선택 → DFS(10, 3)
└─ 더 이상 못 감 → max = 3그래서 정답은 3개이다.
