문제 분석
1. 각 던전의 입장 제한 피로도와 소모 피로도가 담긴 배열이 주어진다(dengeons)
2. 총 제한 피로도가 주어진다(k)
3. 이때 가장 많은 던전을 탐험할 수 있는 방법은 몇 가지 던전을 탐험 가능할까?
뭔가 익숙한 주제이다. 예전에 하던 게임중에 이런 시스템이 있었다.
그 게임의 피로도 시스템은 이렇게 코딩되어 있었겠구나.ㅋㅋ
문제 접근
1. 주제가 완전탐색이어서 DFS/BFS를 사용할 지 반복문을 사용할 지 정해야 한다.
2. 그런데 DFS는 아직 익숙하지가 않았다. (초기 배치를 어떻게 해야 할 지..)
3. dengeons 배열을 순서 있게 정렬한 후에, 각 경우에 대해 모두 탐색한다.생각해볼 문제 1. 완전탐색을 하지 않고도 해답을 구할 수 있는 방법이 있을까? 2. 모든 순열에 대해 탐색을 한다면 복잡도가 지나치게 높아지지 않을까? 3. DFS방식과 순열탐색 방식은 효율 측면에서 얼마나 차이가 날까?
작성한 코드
아무튼 코드를 작성 해보았다. 아무래도 파이썬이다 보니 이 방식이 가장 편해보였다.from itertools import permutations as perm def solution(k, dungeons): clear = 0 way = list(perm(dungeons,len(dungeons))) for arr in way: tired = k cleared = 0 for j in arr: if tired >= j[0]: tired -= j[1] cleared += 1 if clear < cleared: clear = cleared return clear
응? 생각보다 효율성이 좋다
아무래도 dengeons의 길이가 짧기 때문일까?하지만 그래도 DFS로 푸는 방법도 알아야 한다.
왜 why?
JavaScript에는 import permutations이 없으니까.....따라서 이 포스팅에서는 javascript로 permutations을 구현하는 방법과,
DFS를 통해서 푸는 방법을 모두 다룰 예정이다.
다른 사람의 풀이 - DFS
answer = 0 N = 0 visited = [] def dfs(k, cnt, dungeons): global answer if cnt > answer: answer = cnt for j in range(N): if k >= dungeons[j][0] and not visited[j]: visited[j] = 1 dfs(k - dungeons[j][1], cnt + 1, dungeons) visited[j] = 0 def solution(k, dungeons): global N, visited N = len(dungeons) visited = [0] * N dfs(k, 0, dungeons) return answer
코드를 한번 해석 해보자.
1.dfs
부분0-1. 전역변수로 선언된 visited 배열은 dengeons의 길이만큼 0으로 채워놓은 배열이다. 0-2. 전역변수로 선언된 N은 dengeons의 길이이다. 1. dfs 함수는 피로도, count, dengeons배열을 요소로 받는다. 2. dangeons의 길이만큼 탐색을 시도한다. 3-1) 피로도가 dunjeons의 입장 제한 피로도보다 높고, 방문한 적이 없다면 3-2) visited[j] = 1 ...이건 왜? 3-3) 피로도는 dunjeons의 소모 피로도만큼 감소, count는 +1하여 재귀함수 호출 3-4) visited[j] = 0 ...이건 왜? 4. 전역변수로 선언된 answer에 대해서, cnt가 answer보다 크면 값을 교체해준다.
solution
부분1. N, visited를 전역변수로 선언한다. (위의 0-1, 0-2로 설명 하였음) 2. 선언한 dfs함수를 호출한다 3. 최종적으로 남아있는 answer 값을 정답으로 제출한다.
다른 부분은 직관적으로 이해가 되는데,
dfs부분의 3-2, 3-4에 visited[j]를 활용한 부분이 살짝 이해가 가지 않는다.visited를 1로 바꿔주고 재귀를 실행해주고 재귀가 끝나면 visited를 0으로 돌려주고?
효율성 비교
DFS의 시간복잡도 :
permutations의 시간복잡도 :
dfs를 조금 더 연습해야 할 것 같다...
--------------------------------아래 코드 출처 링크--------------------------------
번외 - JavaScript의 순열 구현
const getPermutations = function (arr, selectNumber) { const results = []; if (selectNumber === 1) return arr.map((el) => [el]); arr.forEach((fixed, index, origin) => { const rest = [...origin.slice(0, index), ...origin.slice(index+1)] const permutations = getPermutations(rest, selectNumber - 1); const attached = permutations.map((el) => [fixed, ...el]); results.push(...attached); }); return results; }
번외 - JavaScript의 조합 구현
const getCombinations = function (arr, selectNumber) { const results = []; if (selectNumber === 1) return arr.map((el) => [el]); arr.forEach((fixed, index, origin) => { const rest = origin.slice(index + 1); const combinations = getCombinations(rest, selectNumber - 1); const attached = combinations.map((el) => [fixed, ...el]); results.push(...attached); }); return results; }