5강 재귀 2번 요리사 문제

2주만에 통과하는 알고리즘 코딩테스트 (2024년)

해결된 질문

작성

146

안녕하세요,

강의 전에 풀었을 때 다음과 같은 코드를 작성했는데 정답 인덱스가 비어있게 나오네요.

혹시 왜 이런건지 알 수 있을까요?

강의자료에 있는 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)

python 코딩-테스트 알고리즘

답변 2

코딩 센세

지식공유자

ㅎㅎ 제가 혼자 공부할 때 짰던 코드랑 거의 동일해서 놀랐습니다..

먼저 문제를 말씀드리자면 초기화를 사용하고 있는 것 자체가 문제입니다..!

( 초기화 함수가 정확하게 경우의 수 탐색 전과 후를 구분해 주지 못하고 있습니다. )

경우의 수 탐색 순서가 마지막까지 모든 재료를 사용 -> 초기화 -> 하나의 재료를 사용하지 않음 으로 이어지기 때문에 초기화가 아니라 사용하지 않는 재료만 초기화를 해줘야 합니다!

그러니 지금 코드에서는 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 인턴

안녕하세요, 인프런 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)

이렇게 수정하면, 각 단계에서 선택한 재료의 인덱스를 관리하며, 결과적으로 조건을 만족하는 최소 비용의 재료 조합의 인덱스를 정확하게 얻을 수 있습니다.

인프런 커뮤니티 질문&답변

5강 재귀 2번 요리사 문제