[JavaScript] 프로그래머스 코딩테스트 레벨 2 : 피로도

📌  문제

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

📌  제한사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.

📌  입출력 예

k	dungeons	result
80	[[80,20],[50,40],[30,10]]	3

---

📌  풀이

알아야 하는 것

• Array() : []로 배열을 생성한 것과 동일하게 새로운 배열 생성. 괄호 안에 숫자를 넣으면 해당 숫자만큼 길이가 정해진다.
• array.fill() : 배열의 시작 인덱스부터 끝 인덱스 이전까지 정적인 값 하나로 채운다. 괄호 안에 채울 값을 입력한다.
• 재귀함수: 간단하게 자기 자신을 호출하는 함수로 특정 조건으로 반복을 종료하지 않으면 스택 오버 플로가 발생한다.

 

재귀함수 + dfs 문제를 처음 풀어봐서 너무나 어려웠다. 🤯

dfs는 깊이 탐색이라고 bfs가 같은 레벨의 노드를 탐색한다면 dfs는 하위 노드를 타고 타고 내려가는 형태라고 알고 있다. 

 

function solution(k, dungeons) {
  let answer = [];
  let visited = Array(dungeons.length).fill(false); // [f, f, f]

  // 던전 돈 횟수랑 체력
  function dfs(count, k) {
    answer.push(count);
    console.log(answer);
    for (let i = 0; i < dungeons.length; i++) {
      // 현재 있는 던전
      let current = dungeons[i];
      // 체력 가능하고 안 들린 던전이면 들렸으니까 true
      // 들리고 나면 던전 돈 횟수 +1, 체력 계산 완료
      if (k >= current[0] && !visited[i]) {
        visited[i] = true;
        dfs(count + 1, k - current[1]);
        visited[i] = false;
      }
    }
  }

  dfs(0, k);

  return Math.max(...answer);
}

 

제일 우측에 D2 위에는 10 -> 40이다! 결과에 영향을 주진 않지만 50-10 = 40인데 잘못 적음

 

맨 처음 주어진 유저의 현재 피로도는 80이다.

던전이 3개가 있는데 1번 던전 -> 2번 던전 -> 3번 던전 순으로 방문하면 3번째 던전은 방문할 수가 없어 최대 2개 던전만 방문할 수 있다. 반면 1번 던전 -> 3번 던전 -> 2번 던전 순으로 방문하면 공교롭게도 모든 던전을 방문해 최대 3개 던전을 방문할 수 있다. 

 

바로 이렇게 방문하는 형태의 문제를 주로 재귀함수 + dfs로 해결하는 듯 하다. 어렴풋이 어려운 문제 풀이를 보면서 그런가보다 했는데 내가 하려니까 전혀 이해가 되지 않아 다른 분들의 풀이를 보고 저렇게 하나하나 탐색해 가면서 이해를 해봤다.

 

재귀를 계속 하면 헷갈리게 되는데, 크게 for문을 순회할 때 더 이상 순회할 수 없을 때 해당 함수를 종료하고 그 상위 함수에서 for문을 순회하는 개념이라고 이해했다. 

 

던전을 돈 횟수를 넣어줄 배열 answer와 던전 방문 여부를 표시하기 위해 던전의 갯수만큼 false로 채워진 배열 visited을 세팅했다. 던전은 총 3개로 [[80, 20] [50, 40] [30, 10]] 이렇게 3개가 있다.

 

 

처음 dfs 함수를 실행 시키고 for문을 돌 때 i = 0이다. 이 때 0번째 던전인 [80, 20]을 방문할 수 있다. 초기 피로도가 80이기 때문에 방문할 수 있고, 방문했으니 visited의 i번째 요소를 true로 바꿔둔다. 또 이제 1번 방문했고, 피로도를 계산한 후 dfs에 파라미터로 전달한다. 이렇게 해야 그 하위 노드로 연이어 갈 수 있기 때문이다. 예컨대 상위 그림처럼 D1 -> D2 -> D3으로 1번 2번 3번 방문할 것이니 이 방문 횟수를 push해준다.

 

dfs(1, 60)으로 또 하위 노드, 다음 던전을 방문한다. 남은 던전은 1번째 던전과 2번째 던전인데 인덱스 순으로 돌아가게 되니 i = 0를 먼저 확인한다. 이 때 [true, false, false]로 되어 있어 i = 0은 넘어가고, i = 1을 확인한다. [50, 40] 던전을 돌 수 있게 되면서 [true, true, false]가 되고 dfs(2, 20)이 된다. 

 

다 시 한 번 더 탐색할 때 i = 0, i = 1을 탐색하지만 둘 다 true로 되어 있다. i = 2로 2번째 던전을 방문하려 하지만 최소 피로도 조건에 부합하지 않는다. 더 이상 돌 인덱스가 없으므로 dfs(2, 20)은 종료되고, dfs(2, 20)을 만들기 전이었던 인덱스를 확인한다. 그 때 인덱스는 i = 1로, 밑으로 내려가지 않고 i를 증가시켜 새로운 dfs를 만든다.

 

dfs(1, 60)일 때 i = 2를 보면 2번째 던전을 돌 수 있게 된다. dfs(1, 60)일 때 visited = [true, false, false]였다. 2번째 던전을 돌면서 visited = [true, false, true]가 되고, dfs(2, 50)이 된다. 

 

dfs(2, 50)를 시작함에 따라 i를 0부터 다시 돈다. i = 0은 이미 true라 넘어가고, i = 1번째로 1번째 던전을 보니 [30, 10]으로 방문할 수 있다. dfs(3, 40)이 되면서 또 i를 0부터 돌려고 하지만 이미 모든 visited의 원소가 true가 되어 순회할 수 없게 된다. 

 

dfs(3, 40)를 부르기 전인 dfs(2, 50)으로 올라가도, dfs(2, 20)으로 올라가도, dfs(1, 60)으로 올라가도 더 이상 전개할 것이 없으므로 가장 먼저 진행되었던 for i = 0의 를 증가 시켜 1번째 던전부터 탐색하도록 한다. 

 

지금까지 한 게 1번째 던전 -> 2번째 던전 -> 3번째 던전 (실패) 와 1번째 던전 -> 3번째 던전 -> 2번째 던전의 과정이다.

 

answer = []
visited = [false, false, false]

dfs(0, 80)
answer = [0]
for i = 0 : [80, 20] 던전 돌 수 있음 -> visited = [true, false, false]
	dfs(1, 60)
	answer = [0, 1]
		for i = 0 : visited에 이미 0번째 true임
		for i = 1 : [50, 40] 던전 돌 수 있음 -> visited = [true, true, false]
			dfs(2, 20)
			answer = [0, 1, 2]
				for i = 0 : visited에 이미 0번째 true임
				for i = 1 : visited에 이미 1번째 true임
				for i = 2 : [30, 10] 던전 돌 수 없음 (종료)
		for i = 2 : [30, 10] 던전 돌 수 있음 -> visited = [true, false, true]
			dfs(2, 50)
			answer = [0, 1, 2, 2]
			for i = 0 : visited에 이미 0번째 true임
			for i = 1 : [50, 40] 던전 돌 수 있음 -> visited = [true, true, true] 
				dfs(3, 10)
				answer = [0, 1, 2, 2, 3]
					for i = 0 : visited에 이미 0번째 true임
					for i = 1 : visited에 이미 1번째 true임
					for i = 2 : visited에 이미 2번째 true임 (종료)

 

이제 2번째 던전을 첫 시작으로 2번째 던전 -> 1번째 던전 -> 3번째 던전 으로 가보고, 2번째 던전 -> 3번째 던전 -> 1번째 던전으로 가게 될 것이다. 이 과정이 끝나면 또 3번째 던전을 첫 시작으로 순회하게 된다. 

 

answer = []
visited = [false, false, false]

dfs(0, 80)
answer = [0]
for i = 0 : [80, 20] 던전 돌 수 있음 -> visited = [true, false, false]
	dfs(1, 60)
	answer = [0, 1]
		for i = 0 : visited에 이미 0번째 true임
		for i = 1 : [50, 40] 던전 돌 수 있음 -> visited = [true, true, false]
			dfs(2, 20)
			answer = [0, 1, 2]
				for i = 0 : visited에 이미 0번째 true임
				for i = 1 : visited에 이미 1번째 true임
				for i = 2 : [30, 10] 던전 돌 수 없음 (종료)
		for i = 2 : [30, 10] 던전 돌 수 있음 -> visited = [true, false, true]
			dfs(2, 50)
			answer = [0, 1, 2, 2]
			for i = 0 : visited에 이미 0번째 true임
			for i = 1 : [50, 40] 던전 돌 수 있음 -> visited = [true, true, true] 
				dfs(3, 10)
				answer = [0, 1, 2, 2, 3]
					for i = 0 : visited에 이미 0번째 true임
					for i = 1 : visited에 이미 1번째 true임
					for i = 2 : visited에 이미 2번째 true임 (종료)
for i = 1 : [50, 40] 던전 돌 수 있음 -> visited = [false, true, false]
	dfs(1, 40)
	answer = [0, 1, 2, 2, 3, 1]
		for i = 0 : 조건에 맞지 않음 (종료)
		for i = 1 : 	visited에 이미 1번째 true임
		for i = 2 : [30, 10] 던전 돌 수 있음 -> visited = [false, true, true]
			dfs(2, 30)
			answer = [0, 1, 2, 2, 3, 1, 2]
				for i = 0 : 조건에 맞지 않음 (종료)
for i = 2 : [30, 10] 던전 돌 수 있음 -> visited = [false, false, true]
	dfs(1, 70)
	answer = [0, 1, 2, 2, 3, 1, 2, 1]
	for i = 0 : 조건에 맞지 않음 (종료)
	for i = 1 : [50, 40] 던전 돌 수 있음 -> visited = [false, true, true]
		dfs(2, 30)
		answer = [0, 1, 2, 2, 3, 1, 2, 1, 2]
		for i = 0 : 조건에 맞지 않음 (종료)

answer의 max = 3

그 전체 과정이 위와 같다. 이 때 던전을 몇 개 순회했는지를 answer에 push해주었는데, 가장 많은 던전을 순회한 건 몇 개인지 max로 최종 답을 찾을 수 있다. 그림으로 그리거나 일일이 순회하는 개념으로 이해하지 않으면 나 어디까지 왔더라 하고 꼬이게 된다; 또 함수를 종료하고 나면 visited[i] = false 이 부분을 잊으면 안된다... 이걸 해놔야 이전 상태로 돌아갈 때 여기를 다시 방문할 수 있기 때문이다.

 

하 진짜 어렵다!

오늘 이 문제로 하루종일 싸맸는데 일단 맛을 좀 봤다고 생각해야겠다.

완전 기운 없어... ㅠㅠ 대체 이런 문제는 어떻게 푸는 걸까 ㅋㅋ 어제 했던 완전탐색은 완전 선녀였다...