[파이썬 알고리즘 문제풀이] - Section7 / 깊이/넓이 우선 탐색(DFS, BFS ) 활용 - 1

최대점수 구하기(DFS)

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)

▣ 입력설명
첫 번째 줄에 문제의 개수N(1<=N<=20)과 제한 시간 M(10<=M<=300)이 주어집니다.
두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.

▣ 출력설명
첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.

▣ 입력예제 1
5 20
10 5
25 12
15 8
6 3
7 4

▣ 출력예제 1
41

import sys
# sys.stdin = open("input.text", "rt")
sys.setrecursionlimit(10000)

n,m = map(int, input().split())
data = []
for i in range(n):
    a,b = map(int, input().split())
    data.append((a,b))

data = sorted(data, key = lambda x : x[1])

res = 0 #최대 점수
#한번 푼 문제는 다시 못 푸니까
def DFS(L, sum, time):
    global res 
    if time > m:
        return
    if L == n: #전체 다 확인. 종료조건
        if sum > res:
            res = sum
    else: #아직 전체 다 확인 안했으니 현재 문제 풀 지 안풀지 선택
        DFS(L+1, sum + data[L][0], time + data[L][1]) #푼다
        DFS(L+1, sum, time) #안푼다
        
DFS(0,0,0)
print(res)
        

코멘트

지금까지 이런 유형 많이 봤다. 데이터에 저장한 후에 인덱스를 돌면서 해당 문제(인덱스) 풀 지 안풀 지 (속할지, 안속할지) 부분집합 문제랑 같다고 생각하면 된다.

• 그렇기에 위 코드처럼 DFS-문제 품, DFS-문제 안품 두 번 나눠서 해주면 끝!