프로그래머스_피로도

문제

https://programmers.co.kr/learn/courses/30/lessons/87946?language=python3 

코딩테스트 연습 - 피로도

풀이

깊이 탐색

root_node = [지나간 던전들의 index, 잔여 mp, 지나간적 없는 던전들의 index]

stack = [root_node]

1) answer에 지금까지 지나온 던전 수의 최대값을 저장한다.

2) 모든 던전을 다 지났다면, 탐색을 종료한다.

3) 지나간적 없는 던전 중 조건에 맞는 던전이 있다면, stack에 추가한다.

코드

def solution(k, dungeons):
    # 지나간 던전들의 인덱스, 잔여 mp, 지나간적 없는 던전들의 인덱스
    stack = list()
    stack.append([list(), k, set(range(len(dungeons)))]) 
    answer = 0 # 접근 가능한 던전의 수 (최대값)
    
    while stack : 
        path, mp, notPassed = stack.pop()
        answer = max(answer, len(path)) 
        
        # 모든 던전을 다 지난 경우, 탐색 종료
        if answer==len(dungeons) : break 
            
        for n in notPassed : 
            need, use = dungeons[n]
            if need<=mp and use<=mp : # 잔여 mp 값 검증 
                newNode = [path+[n], mp-use, notPassed-{n}]
                if newNode not in stack : # 기존에 지난 적 없는 경로라면, stack에 추가하기
                    stack.append(newNode)   
    return answer

 

기타

1. 시간 초과

1) 너비우선탐색으로 해결하려 하니 case 8번에서 시간초과가 발생했다. deque 모듈을 사용해도 해결되지 않았다. 깊이 우선 탐색으로 변경하여 해결 했다.

# 시도1 :너비우선탐색

def solution(k, dungeons):
    stack = list()
    stack.append([list(), k]) 
    answer = 0
    
    while stack : 
        path, power = stack.pop(0) # 너비우선
        answer = max(answer, len(path))
        if answer==len(dungeons) : break
            
        notPassed = set(range(len(dungeons)))-set(path)
        for n in notPassed : 
            need, use = dungeons[n]
            if need<=power and use<=power : 
                newNode = [path+[n], power-use]
                if newNode not in stack : 
                    stack.append(newNode)   
    return answer

시도1 : 너비우선탐색

 

2) 지나간 적 없는 던전들의 index를 매번 계산하니 연산 시간이 오래 걸렸다. set() 형태로 queue 안에 넣어서 문제를 해결했다.

# 시도2 : 지나간 적 없는 노드를 매번 계산

def solution(k, dungeons):
    stack = list()
    stack.append([list(), k]) 
    answer = 0
    
    while stack : 
        path, power = stack.pop()
        answer = max(answer, len(path))
        if answer==len(dungeons) : break
            
        notPassed = set(range(len(dungeons)))-set(path) # 계산
        for n in notPassed : 
            need, use = dungeons[n]
            if need<=power and use<=power : 
                newNode = [path+[n], power-use]
                if newNode not in stack : 
                    stack.append(newNode)   
    return answer

시도2 : set으로 매번 계산

 

stack에 지나온적 없는 노드를 미리 저장

 

2. 문제 이해하기

예를 들어 현재 피로도가 80일때,
소모 피로도가 20인 던전을 탐험한 후에는 남은 피로도는 60이다.

위 문장이 직관적으로 이해가 되지 않아서 피로도 대신 Magic point, Mana Point 정도로 이해했다.