[프로그래머스] 피로도

dfs로 풀어보려했으나.. 잘 모르겠음. 나는 역시 아직도 dfs 쪼랩이다.

그래서 일단 풀긴 풀어야하니 굉장히 극극극 비효율로 풀었다. 완전탐색...

 

from itertools import permutations

def solution(k, dungeons):
    answer = []
    orders = list(permutations([i for i in range(0, len(dungeons))]))
    for order in orders:
        score = k
        count = 0
        for i in order:
            if score >= int(dungeons[i][0]):
                score = score - int(dungeons[i][1])
                count = count + 1
        answer.append(count)

    return max(answer)

흠... 

 

내가 dfs를 쓰지 못했던 이유는 backtracking을 생각하지 못했기 때문이다.

이미 방문했던 원소를 visited[i] = 1로 두면 다시 뒤 돌아 나와야할 때는 어떻게 할지 (이게 백트래킹인 것도 몰랐음)에 대한 아이디어가 없었기 때문이다.

 

다른사람의 풀이에 달린 댓글을 보고 이게 백트래킹이라는 것을 알았다. 

answer = 0
N = 0
visited = []


def dfs(k, cnt, dungeons):
    global answer
    if cnt > answer:
        answer = cnt

    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

나는 이렇게 풀고 싶었다. 

흠.. 내일은 백준에서 백트래킹 문제들(8개)를 쭉 풀어보면서 익혀봐야겠다.