[프로그래머스] 피로도 – 87946

완전탐색을 사용하여서 문제를 해결하는 87946에 대해서 작성하겠습니다.

– 87946번 flowchart

1. 알고리즘 설명

알고리즘은 깊이 우선 탐색(DFS)을 사용하여 모든 가능한 던전 조합을 탐색하고, 주어진 체력 범위 내에서 탐험할 수 있는 최대 던전 수를 결정합니다.

2. 코드 설명

• 입력: 사용자의 초기 체력 k, 각 던전의 진입 조건과 소모 체력이 담긴 리스트 dungeons
• 출력: 탐험할 수 있는 최대 던전 수

2.1 전역 변수

• visited: 방문한 던전의 인덱스를 기록하는 리스트. 백트래킹 과정에서 이 리스트를 업데이트하여 이미 탐색한 경로를 피합니다.

2.2 함수 dfs(k, dungeons, count)

DFS 알고리즘의 핵심으로, 가능한 모든 던전 조합을 탐색하여 최대 탐험 가능 던전 수를 찾습니다.

2.3 함수 solution(k, dungeons)

사용자의 초기 체력 k와 던전 리스트 dungeons를 입력받아, dfs 함수를 호출합니다. 이 함수는 최대 탐험 던전 수를 계산하여 반환합니다.

매개변수

• k: 현재 남은 체력.
• dungeons: 던전 리스트, 각 던전은 [진입 조건 체력, 소모 체력]의 형태로 표현됩니다.
• count: 현재까지 탐험한 던전 수.

로직

1. 체력 검사: 현재 체력이 0 이하인 경우, 더 이상 던전을 탐험할 수 없으므로 현재까지의 던전 수에서 1을 빼 반환합니다.
2. 던전 탐색: 모든 던전을 순회하면서, 아직 방문하지 않았고 현재 체력으로 진입 가능한 던전을 찾습니다.
3. 재귀적 탐색: 조건을 만족하는 던전을 찾으면 해당 던전을 방문한 것으로 표시하고, 남은 체력으로 다음 던전을 탐색합니다.
4. 백트래킹: 한 던전의 탐색이 끝나면, 이전 상태로 돌아가 다른 던전을 탐색할 수 있도록 방문한 던전을 방문하지 않은 상태로 되돌립니다.

5. 87946번 코드

• 87946번의 코드와 테스트 케이스입니다.

visited = []  # 방문한 던전을 기록할 리스트

# dfs 함수 정의: 현재 체력(k), 던전 리스트(dungeons), 현재까지 탐험한 던전 수(count)
def dfs(k, dungeons, count):
    if k < 0:  # 현재 체력이 0보다 작으면 탐색을 중단
        return count - 1  # 마지막 던전에서 실패했으므로 탐험한 던전 수에서 1을 빼서 반환

    max_count = count  # 현재까지 탐험한 최대 던전 수
    for i in range(len(dungeons)):  # 모든 던전에 대해 반복
        if i not in visited and k >= dungeons[i][0]:  # 아직 방문하지 않은 던전이고, 체력이 던전 진입 조건을 만족하면
            visited.append(i)  # 방문 리스트에 던전 번호 추가
            # DFS 수행: 남은 체력에서 현재 던전 소모 체력을 빼고, count에 1을 더함
            max_count = max(max_count, dfs(k - dungeons[i][1], dungeons, count + 1))
            visited.pop()  # 현재 던전 방문을 취소 (백트래킹)

    return max_count  # 탐색을 마치고 최대 탐험 던전 수 반환

# solution 함수 정의: 초기 체력(k)과 던전 리스트(dungeons)를 입력받음
def solution(k, dungeons):
    result = dfs(k, dungeons, 0)  # dfs 함수를 호출하여 결과를 계산
    return result  # 결과 반환

6. 트러블

87946 의 재귀적 호출이 아직 익숙하지 않아 재귀를 구현하는데 시간이 많이 들었다.