[programmers] > 완전탐색 > 피로도

문제 바로가기

JAVA

DFS를 이용한 풀이

class Solution {
	public int answer = 0;
	public boolean visited[]; //방문한 던전을 표시한다

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

		visited = new boolean[dungeons.length];
		dfs(0,k,dungeons);

		return answer;
	}

	public void dfs(int visit, int k, int[][] dungeons) {
		int len = dungeons.length;
		for(int i=0;i<len;i++) {
            // 피로도 조건을 충족하면서, 방문하지 않은 던전
			if(dungeons[i][0] <= k && !visited[i]) {
				visited[i] = true;
				dfs(visit+1, k-dungeons[i][1], dungeons);
				visited[i] = false;
			}
		}
		answer = Math.max(answer, visit); //최대 던전의 수
	}
}

---

JAVASCRIPT

DFS를 이용한 풀이

var answer = 0;
var visited; //방문한 던전을 표시한다
function solution(k, dungeons) {
  visited = new Array(dungeons.length);
  dfs(0, k, dungeons);
  return answer;
}

function dfs(visit, k, dungeons) {
  var leng = dungeons.length;
  for (var i = 0; i < leng; i++) {
    // 피로도 조건을 충족하면서, 방문하지 않은 던전
    if (k >= dungeons[i][0] && !visited[i]) {
      visited[i] = true;
      dfs(visit + 1, k - dungeons[i][1], dungeons);
      visited[i] = false;
    }
  }
  answer = Math.max(answer, visit);
}

---

회고하기

아직 dfs, bfs를 완벽하게 이해하지 못한 것 같다.

다음에 정리해서 블로그에 올려야겠다.

---

다른 사람 풀이