[알고리즘] 완전 탐색

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

프로그래머스

 

1. "피로도" 라는 프로그래머스 문제에서 완전 탐색을 요구한다.

• 문제 설명은 위 링크가 있으니 따로 하지는 않는다.

2. 모범 답안

class Solution {
	static boolean[] checked;
	static int cnt = 0;

	public int solution(int k, int[][] dungeons) {

		checked = new boolean[dungeons.length];
		dfs(0, k, dungeons);
		return cnt;
	}

	public void dfs(int depth, int fatigue, int[][] dungeons) {
		for (int i = 0; i < dungeons.length; i++) {
			if (checked[i] || dungeons[i][0] > fatigue) {
				continue;
			}
			checked[i] = true;
			dfs(depth + 1, fatigue - dungeons[i][1], dungeons);
			checked[i] = false;
		}

		cnt = Math.max(cnt, depth);
	}
}

• 이 문제는 모든 경우의 수를 다 따져야한다.
• 전이 3개 있다면 아래와 같이 6개의 순차적인 경우를 다 훑어봐야하는 것이다.
  • 123,132,132,213,231,312,321
• 던전 n 개에 대하여 총 경우의 수가 n!만큼 증가한다.

3. 해석

• 재귀 함수를 통해 모든 던전을 돌거나 더이상 탐험할 수 없게 된 경우에만 탈출하게 된다.
  • if 문의 "checked[i] || dugeons[i][0] > fatigue" 를 통해서 말이다.
• 아주 단순하게 맨 처음123456 사이클을 돌았다고 하면 checked의 모든 원소가 true로 바뀐다. 이것들을 다시 false로 바꿔주어야 다음 사이클을 돌 수 가 있다. 그래서 dfs 다음에 cheked[i] = false를 통해 checked를 원상 복구 해준다.
•  cnt를 이전까지의 최대 탐색 범위(답)로 두고 탐색 깊이 depth 중 더 큰 경우를 비교하여 교체하게 된다.