❓ 프로그래머스 : 피로도

📈 문제 요약

던전의 정보가 [입장 최소 피로도, 소요 피로도]로 주어질 때, 클리어 가능한 던전의 수를 구하면 되는 문제

💻 풀이 1 : permutation을 활용한 풀이

🤨 접근법

첫 번째 풀이는 순열을 활용한 풀이이다. 가능한 모든 순서로 던전을 방문해보고, 방문 가능한 횟수만 카운트 해준다.

던전의 방문 순서는 파이썬의 라이브러리 중 하나인 itertools 모듈의 permutations 메소드를 활용했다. itertools.permutations(collection, n)의 형태로 활용하면 collection에서 n개를 뽑아 가능한 순서를 모두 나열한다.

가능한 순서를 큐에 넣고 다음 던전(queue[0][0])에 방문 가능할 때(피로도 ≥ 입장 최소 피로도)만 큐에서 빼어 카운트 해준 후 피로도를 소요 피로도만큼 감소시키고 카운트를 증가시키는 것을 반복한다.

🔡 코드

def solution(k, dungeons):      # solution using permutation
    permu = permutations(dungeons, len(dungeons))
    answer = 0
    for case in permu:
        queue = deque(case)
        HP = k
        count = 0
        while queue and HP >= queue[0][0]:
            dungeon = queue.popleft()
            HP -= dungeon[1]
            count += 1
        answer = max(answer, count)

    return answer

💻 풀이 2 : dfs & 백트래킹을 활용한 풀이

🤨 접근법

두 번째 풀이는 dfs와 백트래킹을 활용한 풀이이다. 아무래도 순열을 활용하면 불필요한 방문이 너무 많아져 효율적이지 못하다.

예를 들어 던전이 [1, 2, 3, 4, 5]가 있을 때 1 → 2 → 3 까지만 방문 가능할 경우, 이를 알아도 순열을 활용하면 모든 경우를 고려하기 때문에 굳이 1 → 2 → 3 → 4 or 5를 방문하는 경우까지 계산할 것이다.

백트래킹을 활용하면 위와 같은 경우에서 1 → 2 → 3 까지만 방문 가능하다는걸 알았을 때 더 이상 탐색을 진행하지 않고 해당 루트는 탐색하지 않는다. 이를 가지치기라고 한다.

visited 배열과 정답을 관리할 변수 answer를 전역 변수로 선언해주고 dfs를 실행한다.

dfs에서는 특정 던전이 아직 방문하지 않았으며, 해당 던전에 입장 가능하면(피로도 ≤ 입장 최소 피로도) 방문 처리 후 재귀로 다시 dfs를 실행한다. 모든 던전에 방문 처리 되거나, 특정 던전에 입장이 불가할 때까지 재귀를 실행하며, 재귀가 종료된 후에는 해당 던전의 방문처리를 False로 바꿔 다음 루트를 탐색할 수 있도록 하였다.

프로그래머스에서는 기본적으로 solution함수에서 정답을 반환하도록 구현해야하기 때문에 전역변수를 활용할 때 함수에 global 선언을 꼭 빼먹으면 안된다.

🔡 코드

visited = []
answer = 0

def dfs(HP, dungeons, count):
    global answer

    if answer < count:
        answer = count

    for i in range(len(dungeons)):
        if not visited[i] and dungeons[i][0] <= HP:
            visited[i] = True
            dfs(HP - dungeons[i][1], dungeons, count + 1)
            visited[i] = False

def solution1(k, dungeons):     # solution using backtracking
    global answer, visited

    visited = [False for _ in range(len(dungeons))]
    dfs(k, dungeons, 0)

    return answer