[파이썬] 프로그래머스 피로도 풀이

문제 확인

프로그래머스

나의 풀이

• 던전의 최대 개수는 8개로, 각 던전 방문의 경우의 수는 8! = 40320이기 때문에 완전 탐색만으로도 풀 수 있다.
• 가능한 던전 방문의 순서를 얻기 위해서, 순열을 활용했다.

# 던전 입장 조건 : 피로도 >= 최소 피로도, 던전 입장 후 : 피로도 -= 소모 피로도
# 최소 피로도 >= 소모 피로도
# 최대한 많이 탐험 -> 각 던전은 한번만 가능
# 가능한 경우의 수 : 8! : 40320 -> 완전 탐색으로도 풀 수 있음
from itertools import permutations

def solution(k, dungeons):
    dun_cnt_list = []
    # 방문 순서 확인
    for perm in permutations(range(len(dungeons)), len(dungeons)):
        # 피로도, 방문 수 초기화
        temp_k = k
        dun_cnt = 0
        # 던전 방문
        for i in perm:
            need_k, use_k = dungeons[i]
            # 방문 가능한 경우
            if temp_k >= need_k:
                dun_cnt += 1
                temp_k -= use_k
        # 방문한 던전의 수
        dun_cnt_list.append(dun_cnt)
    # 최대 방문 횟수
    return max(dun_cnt_list)

다른 사람 풀이

• 백트래킹을 활용한 풀이다.
• 기존엔 주석이 없었지만, 이해하기 위해서 주석을 추가했다.

answer = 0
N = 0
visited = []


def dfs(k, cnt, dungeons):
    global answer
    # 최대 방문 횟수 초기화
    if cnt > answer:
        answer = cnt
	# 방문 시작 점 설정
    # DFS로 탐색이 끝나고, 다른 시작 점으로 탐색 시작 
    for j in range(N):
    	# 피로도가 충분해서 방문할 수 있지만, 아직 방문하지 않은 경우
        if k >= dungeons[j][0] and not visited[j]:
        	# 방문 처리
            visited[j] = 1
            # 줄어든 피로도로 던전 방문 시작
            dfs(k - dungeons[j][1], cnt + 1, dungeons)
            # 해당 순서로 던전을 모두 방문했으니, 다시 초기화
            visited[j] = 0


def solution(k, dungeons):
    global N, visited
    N = len(dungeons)
    visited = [0] * N
    dfs(k, 0, dungeons)
    return answer

프로그래머스

---

참고

[실전 알고리즘] 0x0C강 - 백트래킹

• 백트래킹에 대해서 전반적으로 확인할 수 있는 강의다.