[Java] 문제 풀다가 간접적 DFS 알고리즘 경험
프로그래머스에 있는 알고리즘 문제 피로도를 풀다가 고생한 것들을 작성해볼까 한다.
문제에 들어가보면 자세히 적혀 있겠지만 요약해서 적도록 하겠다.
문제 설명
XX게임에는 피로도 시스템이 있으며 일정 피로도를 사용해서 던전을 탐험할 수 있다. 다만 해당 던전에 대한 정보를 담고 있는 dungeons 이라는 변수가 있다고 치자! 해당 던전의 정보는 입장시 "최소 필요 피로도 수치" 와 "소모 피로도" 수치를 가지고 있다. 그리고 한번이라도 탐험한 던전에는 재입장 불가능이며 k 라는 피로도 수치가 주어지면 최대 몇번의 던전을 클리어 할수 있는지 리턴하는 함수를 작성하는 문제이다.
제한 사항
- k는 1 이상 5,000 이하인 자연수
- dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하
- dungeons의 가로(열) 길이는 2
- dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"]
- "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같다
- "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수
- 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있다.
입출력 예
| k | dungeons | result |
| 80 | [[80,20],[50,40],[30,10]] | 3 |
입출력 예 설명
k에서 주어진 피로도는 80로 가정하여 풀어보면 아래와 같다.
만약, 첫 번째 → 두 번째 → 세 번째 순서로 탐험!
- 현재 피로도 : 80 , 첫번째 던전의 "최소 필요 피로도 수치" : 80이고 탐험시 "소모 피로도" 는 20이다. 이에 돌게 되면 80 - 20 = 60 이 남는다.
- 현재 피로도 : 60 , 두번째 던전의 "최소 필요 피로도 수치" : 50이고 탐험시 "소모 피로도" 는 40이다. 이에 돌게 되면 60 - 40 = 20 이 남는다.
- 현재 피로도 : 20 , 세번째 던전의 "최소 필요 피로도 수치"는 30이라 돌수 없다! 따라서 던전은 2번을 돌았다.
다르게 접근한 방식은 아래와 같다.
만약, 첫 번째 → 세 번째 → 두 번째 순서로 탐험!
- 현재 피로도 : 80 , 첫번째 던전의 "최소 필요 피로도 수치" : 80이고 탐험시 "소모 피로도" 는 20이다. 이에 돌게 되면 80 - 20 = 60 이 남는다.
- 현재 피로도 : 60 , 세번째 던전의 "최소 필요 피로도 수치" : 30이고 탐험시 "소모 피로도" 는 10이다. 이에 돌게 되면 60 - 10 = 50 이 남는다.
- 현재 피로도 : 50 , 두번쨰 던전의 "최소 필요 피로도 수치" : 50이고 탐험시 "소모 피로도" 는 40이다. 이에 돌게 되면 50 - 40 = 10 이 남는다.
- 3개의 던전을 모두 돌수 있었기에 최대 던전 수는 3이 된다.
풀이 과정(오답)
문제 설명을 봤을때 처음은 단순하게 생각하여 "최소 필요 피로도 수치" - "소모 피로도" 기준으로 역정렬하면 어떨까 싶어서 문제를 풀어봤다.
코드(오답)
import java.util.*;
class Solution {
public int solution(int k, int[][] dungeons) {
int answer = 0;
// 최소 필요 피로도 , 소모 피로도 = 차이기준으로 역정렬
// 80 - 20 = 60
// 30 - 10 = 20
// 50 - 40 = 10
Arrays.sort(dungeons, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return (o2[0] - o2[1]) - (o1[0] - o1[1]);
}
});
for (int i = 0; i < dungeons.length; i++) {
if (k >= dungeons[i][0]) {
k -= dungeons[i][1];
answer++;
}
}
return answer;
}
}
어째서인지 테스트 케이스 3개나 틀렸고 뭐가 문제인지 찾아보다가 반례를 발견했다.
이는 역정렬 방식으로 해결할수 없던 방식이였다!
반례 입출력 예
| k | dungeons | result |
| 78 | [[78, 18], [70, 11], [67, 9], [60, 8], [59, 2], [57, 54]] | 4 |
반례 입출력 예 설명
던전 탐험 순서 : 첫번째 던전[78, 18] → 다섯번째 던전[59, 2] → 여섯번째 던전[57, 54]
- 현재 피로도 : 78 , 첫번째 던전의 "최소 필요 피로도 수치" : 78이고 탐험시 "소모 피로도" 는 18이다. 이에 돌게 되면 78 - 18 = 60 이 남는다.
- 현재 피로도 : 60 , 다섯번째 던전의 "최소 필요 피로도 수치" : 59이고 탐험시 "소모 피로도" 는 2이다. 이에 돌게 되면 60 - 2 = 58 이 남는다.
- 현재 피로도 : 58 , 여섯번째 던전의 "최소 필요 피로도 수치" : 57이고 탐험시 "소모 피로도" 는 54이다. 이에 돌게 되면 58 - 54 = 4 가 남는다. 이로써 다른 던전을 돌수 없어 최대 돌수 있었던 던전은 3이다.
던전 탐험 순서 : 두번째 던전[70, 11] → 네번째 던전[60, 8] → 다섯번째 던전[59, 2] → 여섯번째 던전[57, 54]
- 현재 피로도 : 78 , 첫번째 던전의 "최소 필요 피로도 수치" : 70이고 탐험시 "소모 피로도" 는 11이다. 이에 돌게 되면 78 - 11 = 67 이 남는다.
- 현재 피로도 : 67 , 첫번째 던전의 "최소 필요 피로도 수치" : 60이고 탐험시 "소모 피로도" 는 8이다. 이에 돌게 되면 67 - 8 = 59 가 남는다.
- 현재 피로도 : 59 , 첫번째 던전의 "최소 필요 피로도 수치" : 59이고 탐험시 "소모 피로도" 는 2이다. 이에 돌게 되면 59 - 2 = 57 이 남는다.
- 현재 피로도 : 57 , 첫번째 던전의 "최소 필요 피로도 수치" : 57이고 탐험시 "소모 피로도" 는 54이다. 이에 돌게 되면 57 - 54 = 3이 남는다. 이로써 다른 던전을 돌수 없어 최대 돌수 있었던 던전은 4이다.
풀이과정(정답)
어떻게 접근 해야할지 몰라서 내일배움캠프 튜터님께 여쭤 보았고 DFS 알고리즘을 통해 접근한다는 것을 알아냈다.
물론 인터넷에 검색해서 나왔던 DFS 알고리즘과는 느낌이 많이 다르지만 깊이 빠져 들어가면서 재귀 함수를 통해 모두 탐색한다는 점에 의해서 비슷했다.
위의 흐름이 깊이 들어가면서 탐색하는 흐름이 DFS 알고리즘의 그림와 흡사했다.
이를 토대로 코드를 재작성 하였다.
코드(정답)
class Solution {
// 전역변수로 설정해서 문제 풀어보는 것은 처음
int max = 0;
public int solution(int k, int[][] dungeons) {
int answer = 0;
// 던전 입장여부를 검증하기 위한 논리 변수
boolean[] entrance = new boolean[dungeons.length];
// dfs 알고리즘
dfs(k, dungeons , entrance , 0);
return max;
}
public void dfs(int k , int[][] dungeons ,boolean[] entrance , int count) {
for (int i = 0; i < dungeons.length; i++) {
// 입장해본 던전이거나 최소 입장 피로도에 못미치거나
if (entrance[i] || k < dungeons[i][0]) {
continue;
}
// 입장처리
entrance[i] = true;
// 소모 피로도 적용 및 count 1 증가 해서 dfs 돌기
dfs(k - dungeons[i][1], dungeons , entrance , count + 1);
// 다른 케이스를 위해 입장 가능하게 변경
entrance[i] = false;
}
// 더 큰 값을 max에 설정 => 이값이 최대 돌수 있는 던전 수가 될 것임
max = Math.max(max , count);
}
}