[Programmers/파이썬] 프로그래머스(Lv.2) 피로도 문제풀이

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

 

사고 흐름

1. dungeons의 최대 길이 8 -> 완전 탐색으로 판단 (아니길 바랬지만)

2. 완전탐색 방법

2-1. dungeons의 모든 순열 조합을 찾고 확인해볼까? -> permutation 

2-2. dfs로 가다가 탐험 불가능 (최소 필요 피로도만큼 부족)할 때 멈추자 -> 백트래킹 (선택)

 

문제 핵심과 알고리즘

완전 탐색 + 백트래킹 

 

def dfs(v, k, visited, dic, dungeons, ans) :
    
    k-=dic[v][1]
    
    if k<0 :
        ans.append(len(visited))
        return visited
    visited.append(v)

    for i in range(len(dungeons)) :
        if k>=dic[i][0] and i not in visited :
            dfs(i, k, visited, dic, dungeons, ans)
            visited.pop()
    
    ans.append(len(visited))
    return visited

def solution(k, dungeons):
    dic = {}
    ans = []
    for i,d in enumerate(dungeons) :
        dic[i] = d
    
    for i in range(len(dungeons)) :
        dfs(i, k, [], dic, dungeons, ans)
    return max(ans)

# 40, [[40, 20], [10, 10], [10, 10], [10, 10], [10, 10]]

 

dic 딕셔너리를 사용해 dungeons에 인덱스를 지정하고 dfs를 실행한다. dfs 함수에서는 k에 소모 피로도를 빼고 만약 음수가 된다면 더이상 갈 수 없으므로 종료한다. 종료되지 않는다면, 방문 처리를 후 방문하지 않고 최소 필요 피로도만큼 있는 노드로 dfs 를 다시 실행한다. 이때 ans.append(len(visited)) 는 해당 경로 탐색이 종료될 때 종료되는 깊이, 즉 탐험 가능한 던전 수를 추가하는 것이다. 여기서 최대값이 정답이 된다. 

 

문제 풀면서 헤맸던 부분

1. visited.pop()

원래 dfs를 구현할 때 방문처리 배열은 건들지 않았다. 근데 처음 코드는 통과를 못했고, 과정을 출력한 결과 visited 배열에서 문제점을 발견했다. 만약 모든 경우가 끝까지 탐색하는 경우라면 필요없었겠지만, 중간에 다시 BACK 해야하는데 이것을 생각하지 못했다. 백트래킹 문제를 많이 풀어야겠다. 익숙해지자! 

 

총평 

(소요시간: 1시간) 자꾸 몇 TC가 틀려서 고치느라 시간이 엄청 걸렸다. dfs는 이제 자신있었는데 익숙하지 않은 유형이라고 바로 버벅거렸다. 틀린 부분 찾으려고 print 했는데도 못찾고, dfs 그래프 그려서 따라가면서 문제점을 찾았다. 재귀는 편하고 간단하지만 그만큼 허점이 많을 수도 있어서 연습이 필요한 것 같다.. 그리고 처음 떠올렸던 순열 방법으로 했으면 훨 빨리 풀었을것 같다. 나중에 순열로 다시 풀어봐야지!