프로그래머스 피로도 (Lv.2)

문제 설명

1. 하루에 한번 만 탐험 할 수 있는 던전들이 있다.
2. 이 던전들은 각각 요구하는 최소 피로도와 탐험 후 소모되는 소모 피로도 값을 가지고 있다.
3. 던전들의 최소 피로도와 소모 피로도 값이 주어질 때
   유저가 탐험할 수 있는 던전의 최대 수를 return 하면 된다.

접근 방법

처음에 그리디 알고리즘을 사용해서 푸는 문젠가 싶었는데 문제의 제한사항을 보니 던전의 개수가 8이하여서 최대 8!(팩토리얼)의 경우의 수가 생기므로 완전탐색으로 충분히 구현 가능하다.

구현 방법

이 문제에서 완전 탐색 순열을 구현하는 데 떠오른 방법은 두 가지다.
1. dfs, bfs를 이용하는 방법
2. 파이썬 itertools라이브러리의 permutations를 이용하는 방법
그 중에서 나는 dfs로 문제를 풀어 보았다.

풀이 코드

answer = 0
visited = []
def enter(dungeons, k, i):
    global answer
    k -= dungeons[i][1]
    answer = max(answer, sum(visited))
    
    for j in range(len(dungeons)):
        if not visited[j] and dungeons[j][0] <= k:
            visited[j] = 1
            enter(dungeons, k, j)
            visited[j] = 0
    
def solution(k, dungeons):
    global visited
    visited = [0] * len(dungeons)
    
    for i in range(len(dungeons)):
        if k >= dungeons[i][0]:
            visited[i] = 1
            enter(dungeons, k, i)
            visited[i] = 0
    return answer

# 1. 그리디로 풀 수 있는 문제 인가?
# 증명 방법 공부하기
# 2. k 값이 작아서 완전탐색해도 되겠다.

시행착오 및 보완점

처음에 visited를 함수 인자로 넣고 풀 때 많이 헤맸다.
파이썬은 함수 인자에 리스트를 넣으면 이것도 얕은복사가 되어 의도하지 않은 동작을 수행하게 된다. 파이썬에서 리스트를 사용할 때 얕은복사를 항상 염두해서 사용해야 할 것 이다.

그리디 알고리즘의 정당성을 증명하는 과정을 좀 더 공부해야 할 필요가 있다.

visited를 인자에 넣고, 깊은 복사를 해 준 코드

answer = 0
def enter(dungeons, k, i, visited):
    global answer
    visited = visited[:]
    visited[i] = 1
    k -= dungeons[i][1]
    answer = max(answer, sum(visited))
    
    for j in range(len(dungeons)):
        if not visited[j] and dungeons[j][0] <= k:
            enter(dungeons, k, j, visited)
    
def solution(k, dungeons):
    visited = [0] * len(dungeons)
    
    for i in range(len(dungeons)):
        if k >= dungeons[i][0]:
            enter(dungeons, k, i, visited)

    return answer