[프로그래머스, 87946번] 피로도 (DFS, Java)

문제설명

입력 & 출력

나의 풀이

이번 "프로그래머스 - 피로도"문제는 다음과 같은 조건을 만족해야 하는 문제입니다.

1. 피로도: 어떤 던전을 탐험하려면 최소 필요 피로도와 소모 피로도가 있습니다.
   • 최소 필요 피로도: 해당 던전을 탐험하기 위해 필요한 최소 피로도 
   • 소모 피로도: 해당 던전을 탐험하면 소모되는 피로도 
2. 목표: 주어진 k(현재 피로도)와 던전 정보가 있을 때, 최대 몇 개의 던전을 탐험할 수 있는지를 구하는 것입니다.

전체 코드

 

이 문제는 완전 탐색으로 해결할 수 있지만, DFS를 활용하면 풀이 과정이 더 간단하고 명확해집니다

 

문제를 해결하기 위해 방문 여부를 확인하는 배열(visited)과 최대 탐험 가능한 던전 수(max)를 선언했습니다. 두 변수는 탐색 과정에서 자주 초기화되기 때문에 static으로 선언하여 관리했습니다.

 

DFS 함수

 

DFS 알고리즘에서는 일반적으로 탈출 조건을 명시적으로 작성합니다. 하지만 이 코드에서는 루프 조건과 방문 여부 체크가 이미 탈출 조건의 역할을 수행하고 있습니다.

 

루프가 종료되거나 탐험 가능한 던전이 없을 경우, 재귀 호출이 더 이상 이루어지지 않고 자연스럽게 반환됩니다. 따라서 별도로 명시적인 탈출 조건을 추가하지 않아도 모든 탐색이 정상적으로 종료됩니다.

 

• 현재 피로도 k로 던전을 탐험할 수 있는지 확인.
• 탐험 가능하면 방문 처리(visited[i] = true)하고 재귀 호출.
• 탐험을 완료하면 백트래킹으로 상태 복구.

k = 80, dungeons = [[80,20],[50,40],[30,10]]가 입력으로 주어졌을 때 DFS 함수가 어떻게 동작하는 지 확인해보겠습니다.

 

초기 호출

dfs(dungeons, 80, 0);

• currentK: 80 (초기 피로도)
• count: 0 (아직 탐험한 던전 없음).

첫 번째 탐험

첫 번째 호출 : 던전 0 - 탐험 시작 (i = 0)

• 0 번째 던전 [80,20] 탐험 가능(k = 80 >= 80)
  • k = 80 - 20 = 60
  • visited = [true, false, false]
  • count = 0 + 1 = 1
  • 재귀 호출 : dfs(dungeons, 20, 1)

두 번째 호출 : 던전  1 - 탐험 시작 (i = 1)

• 1 번째 던전 [50,40] 탐험 가능(k = 60 >= 50)
  • k = 60 - 40 = 20
  • visited = [true, true, false]
  • count = 1 + 1 = 2
  • 재귀 호출 : dfs(dungeons, 20, 2)

세 번째 호출 : 던전  2 - 탐험 시작 (i = 2)

• 2 번째 던전 [30,10] 탐험 불가능(k = 20 < 30)
  • 백트래킹 : 변화 없음, 돌아감
  • k = 20 (남은 피로도 유지)
  • visited = [true, true, false] (현재 방문 상태 유지)
  • count = 1 + 1 = 2 (탐험한 던전 수 유지)
• 백트래킹 후 상태
  • 탐험을 중단하고 이전 호출로 돌아갑니다.
  • 돌아간 후
    • k =60
    • visited = [true, false, false]
    • count = 1

두 번째 호출 : 다른 던전 탐험 시도 (i =2)

• 백트래킹 후 상태
  • 이전 호출로 돌아가서 던전 2를 탐험할 지 확인
  • k = 60
  • visited = [true, false, false]
  • count = 1
• 2 번째 던전 [30,10] 탐험 가능(k = 60 >= 30)
  • k = 60 - 10 = 50
  • visited = [true, false, true]
  • count = 1 + 1 = 2
  • 재귀 호출 : dfs(dungeons, 50, 2)

세 번째 호출 : 던전 1 탐험 시도 (i =1)

• 1 번째 던전 [50,40] 탐험 가능(k = 50 >= 50)
  • k = 50 - 40 = 10
  • visited = [true, true, true]
  • count = 2+ 1 = 3
  • 재귀 호출 : dfs(dungeons, 20, 2)
• 최대 탐험 도달
  • 모든 던전을 탐험했으므로, max = 3갱신
  • 모든 던전을 탐험한 후에는 더 이상 탐험할 던전이 없으므로 해당 for문이 종료됩니다.
  • k = 10
• 백트래킹 시작
  1. 세 번째 호출 종료
     • visited[1] = false로 복원
     • visited = [true, false, true]
     • count = 2로 복원
     • k = 50으로 복원
  2. 두 번째 호출 종료
     • visited[2] = false로 복원
     • visited = [true, false, false]
     • count = 1로 복원
     • k = 60으로 복원
  3. 세 번째 호출 종료
     • visited[0] = false로 복원
     • visited = [false, false, false]
     • count = 0로 복원
     • k = 80으로 복원
• DFS 함수 종료
  • 모든 가능한 던전 탐험 순서를 탐색 완료
  • 최종 max 값 3 반환 이는 [80,20] -> [50,40] -> [30,10] 순서로 탐험하는 경우가 최대 던전 수를 달성할 수 있는 경우의 수임