5강 재귀 2번 요리사 문제

Question

안녕하세요, 강의 전에 풀었을 때 다음과 같은 코드를 작성했는데 정답 인덱스가 비어있게 나오네요. 혹시 왜 이런건지 알 수 있을까요? 강의자료에 있는 pop을 이용하는 방법은 이해했습니다. 먼저 결과창입니다.   6 100 70 90 10 30 55 10 8 100 60 10 10 2 70 10 80 50 0 50 40 30 30 8 60 60 10 70 2 120 20 70 50 4 4 [1, 2, 3, 4, 5] [] [] [] [5] [3, 4, 5] [2, 3, 4, 5] [] [] 134 [] 코드입니다. n=int(input()) std= list(map(int, input().split())) ing=[list(map(int, input().split())) for _ in range(n)] price=1e9 tmp_best=[] best=[] def dfs(idx,a,b,c,d,p,check): global best global tmp_best global price if idx==n: if a>=std[0] and b>=std[1] and c>=std[2] and d>=std[3] : if p<price: price=p best=tmp_best.copy() print(best) tmp_best=[] else: tmp_best=[] return if check==1: tmp_best.append(idx) dfs(idx+1,a+ing[idx][0], b+ing[idx][1], c+ing[idx][2], d+ing[idx][3],p+ing[idx][4],1) dfs(idx+1,a,b,c,d,p,0) dfs(0,0,0,0,0,0,0) print(price, best)

코딩 센세 · Answer

ㅎㅎ 제가 혼자 공부할 때 짰던 코드랑 거의 동일해서 놀랐습니다..   먼저 문제를 말씀드리자면 초기화를 사용하고 있는 것 자체가 문제입니다..! ( 초기화 함수가 정확하게 경우의 수 탐색 전과 후를 구분해 주지 못하고 있습니다. )   경우의 수 탐색 순서가 마지막까지 모든 재료를 사용 -> 초기화 -> 하나의 재료를 사용하지 않음 으로 이어지기 때문에 초기화가 아니라 사용하지 않는 재료만 초기화 를 해줘야 합니다!   그러니 지금 코드에서는 tmp_best=[] 를 해서 모든 재료를 사용하지 않음! 으로 바꾸고 있지만, 사실 그때 해줘야 할 건 초기화가 아닌 하나의 재료만 사용하지 않음! 으로 바꿔줘야 하는 것이죠   백트래킹에서는 해당 경우의 수 탐색 전 후의 코드를 똑같이 맞춰줘야 합니다. ( 미래를 보고 그대로 과거로 돌아오면서 모든걸 되돌려줘야하는 시간 마법사 같은 느낌을 조금 떠올려 보면 이해하기 쉬울까 싶네요.. 🤔 )   visited[idx+1] = 1 # 방문 처리 func(idx+1,p+info[idx][0],f+info[idx][1],s+info[idx][2],v+info[idx][3],sum1+info[idx][4]) visited[idx+1] = 0 # 방문 처리 해제   used.append(idx+1) # 사용 처리 recur(idx+1, p+ing[idx][0], f +ing[idx][1], c + ing[idx][2], v + ing[idx][3], price+ing[idx][4]) used.pop() # 사용 처리 해제   위 코드들과 같이 들어가기 전의 상태로 그대로 복구해줄 수 없다면 재귀를 이용한 경우의 수 탐색은 반드시 실패합니다 🙂   코드를 보니 확실히 이해하신 걸로 보이는데, 당연히 경우의 수를 탐색하는데 함수 속에서 사용 , 사용해제 의 순서대로 구분하는게 아니라 별개의 방법인 초기화 나 글로벌 함수로 관리, 등의 방법을 이용하면 안되겠죠..!   한번 하나의 경우의 수를 탐색한 다음에 그 경우의 수를 탐색하기 전으로 완벽하게 되돌려주는 코드를 작성하시는 게 좋을 것 같습니다.

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. 에밀리님 코드에서 정답 인덱스가 비어있게 나오는 이유는 재귀 호출 과정에서 조건을 만족하는 경우에만 tmp_best 리스트를 복사하여 best 리스트에 저장하고, 그렇지 않은 경로에서 tmp_best 리스트를 초기화하지 않아도 되는데, 잘못된 위치에서 tmp_best 리스트를 초기화하고 있기 때문입니다. 문제를 해결하기 위해, tmp_best=[] 라인을 dfs() 함수 호출 전에 조건을 만족하지 않는 경우에 초기화하는 부분을 제거하고, 함수의 시작 부분에서 tmp_best 변수를 사용하기 전에 재귀적으로 조건을 만족하는 케이스에서 tmp_best 리스트에 idx를 추가하는 방식으로 접근해야 정상적으로 작동합니다. 정답 인덱스가 기대와 다르게 나오는 주된 문제는, 재귀 호출을 끝내고 나올 때 tmp_best 에서 현재 추가한 idx 값을 제거하지 않아서 발생합니다. 재귀 호출이 끝나고 나올 때, tmp_best 리스트에 append 해준 idx 값을 pop 을 이용해서 다시 제거해주는 로직을 추가해야 합니다. tmp_best.append(idx) 를 한 후에 다음 재귀 호출이 끝난 후 tmp_best.pop() 을 통해 해당 인덱스를 다시 제거하는 로직을 추가해보세요. 또한, 최소값을 갱신할 때마다 tmp_best 를 초기화하지 않도록 주의해주세요. 수정된 코드 예제는 다음과 같습니다. def dfs(idx, a, b, c, d, p, check): global best global tmp_best global price if idx == n: if a >= std[0] and b >= std[1] and c >= std[2] and d >= std[3]: if p < price: price = p best = tmp_best.copy() print(best) return if check == 1: tmp_best.append(idx) dfs(idx+1, a+ing[idx][0], b+ing[idx][1], c+ing[idx][2], d+ing[idx][3], p+ing[idx][4], 1) if check == 1: tmp_best.pop() # 현재 추가한 idx를 제거 dfs(idx+1, a, b, c, d, p, 0) 이렇게 수정하면, 각 단계에서 선택한 재료의 인덱스를 관리하며, 결과적으로 조건을 만족하는 최소 비용의 재료 조합의 인덱스를 정확하게 얻을 수 있습니다.