[Java] 완전탐색 - 피로도 (Lv2)

처음에는 배열을 먼저 정렬해야하나 싶었지만 배열의 우선순위로 정렬해도 원하는 답이 나오지 않아 배열 정렬 없이 DFS로 도전했던 문제 🔥

 

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

 

✔ 입출력 예시

피로도 입출력 예시

 

 

1️⃣ 첫번째 시도

❓ 풀이방법

     👉 모든 경우의 수를 구하기 위해 DFS 활용

1️⃣ DFS 함수에 필요한 변수들 넣기 (dungeons, 방문 배열, k, 탐험한 던전 수)

2️⃣ 반복문을 돌리며 완전 탐색 진행 (이미 탐험했던 던전은 ❌, 아니라면 재귀 진행⭕)

3️⃣ 재귀함수로 진입했을 때 k가 음수라면 방금 탐험했던 던전은 현재 피로도로 탐험할 수 없었던 던전이므로,

      지금까지 구한 cnt-1의 값과 지금까지의 최대 던전 횟수를 비교하여 max변수 초기화 후 return

4️⃣ 재귀함수로 진입했을 때 모든 던전을 다 탐험했다면 max 변수는 cnt의 값으로 초기화 후 return

 

❗ 결과

   👉 테스트 3, 7, 14, 15, 16 실패

 

✔ 소스코드

public class Solution { // 피로도

	public static void main(String[] args) {
		int k = 80;
		int[][] dungeons = { { 80, 20 }, { 50, 40 }, { 30, 10 } };

//		int k = 30;
//		int[][] dungeons = { { 20, 20 }, { 50, 40 }, { 30, 10 } };

		System.out.println(solution(k, dungeons));
	}

	private static int solution(int k, int[][] dungeons) {
		// DFS 실행하기
		DFS(dungeons, new boolean[dungeons.length], k, 0);

		return max;
	}

	static int max = -1; // 최대 개수 담기

	private static void DFS(int[][] dungeons, boolean[] v, int k, int cnt) {
		if (k < 0) { // k가 0미만이라면 방금 탐험한 던전을 제외하고 개수 세기
			if (max < cnt - 1) {
				max = cnt - 1;
			}
			return;
		}
		
		if (cnt == dungeons.length) { // 모든 던전을 탐험했다면
			max = cnt;
			return;
		}


		for (int i = 0; i < dungeons.length; i++) {
			if (v[i]) continue; // 이미 탐험한 던전이라면 continue;
			// 방문하지 않은 던전 탐험
			v[i] = true; // 던전 탐험
			DFS(dungeons, v, k - dungeons[i][1], cnt + 1);
			v[i] = false; // 탐험했던 던전 취소
		}
	}
}

 

 

2️⃣ 두번째 시도

❓ 풀이방법

     👉 모든 경우의 수를 구하기 위해 DFS 활용

1️⃣ DFS 함수에 필요한 변수들 넣기 (dungeons, 방문 배열, k, 탐험한 던전 수)

2️⃣ 반복문을 돌리며 완전 탐색 진행

     (이미 탐험했던 던전이거나 남은 피로도가 최소 필요 피로도 미만일 경우 ❌, 아니라면 재귀 진행⭕)

3️⃣ 던전 방문 처리 후 다음 던전에 대해 재귀 실행

4️⃣ 경우의 수 탐색이 끝날 때마다 max값과 cnt값을 비교하여 최댓값 찾기

 

❗ 결과

   👉 테스트 통과

 

✔ 소스코드

public class Solution { // 피로도

	public static void main(String[] args) {
//		int k = 80;
//		int[][] dungeons = { { 80, 20 }, { 50, 40 }, { 30, 10 } };

//		int k = 30;
//		int[][] dungeons = { { 20, 20 }, { 50, 40 }, { 30, 10 } };

//		int k = 40;
//		int[][] dungeons = { { 40, 20 }, { 10, 10 }, { 10, 10 }, { 10, 10 }, { 10, 10 } };

		int k = 5000;
		int[][] dungeons = { { 1000, 1000 }, { 1000, 800 } ,{ 900, 900 }, {1500, 1500}, { 200, 40 }, { 1500, 1000 }};
		
		
		System.out.println(solution(k, dungeons));
	}

	private static int solution(int k, int[][] dungeons) {
		// DFS 실행하기
		DFS(dungeons, new boolean[dungeons.length], k, 0);

		return max;
	}

	static int max = -1; // 최대 개수 담기

	private static void DFS(int[][] dungeons, boolean[] v, int k, int cnt) {

		for (int i = 0; i < dungeons.length; i++) {
			if (v[i]) continue; // 이미 탐험한 던전이라면 continue;
			// 탐험하지 않은 던전 탐험
			if(k >= dungeons[i][0]) {
				v[i] = true; // 던전 탐험
				DFS(dungeons, v, k - dungeons[i][1], cnt + 1);
				v[i] = false; // 탐험했던 던전 취소
			}
		}
		
		max = Math.max(max, cnt);
		return;
	}
}

첫번째 시도의 코드를 조금 더 깔끔하게 정리해보며 재귀함수의 if문을 이용한 기저조건문을 없애주었다.

코드가 더 깔끔해졌고 테스트를 통과할 수 있었다. 

첫번째 시도에서 작성했던 기저조건에 문제가 있었나 봄...😢