[알고리즘] 백트래킹 재귀함수안의 값 재귀함수 밖으로 가지고 나오기

백트래킹 재귀함수에서 항상 부딛히는 문제가 있다. 

 

안에서 만든 리스트를 어떻게 밖으로 꺼내올 것인가? 

1. final에 ans를 그냥 append -> 안됨 빈 리스트 출력

n = int(input())
ans = []
final = []

cnt = 0
def beautiful_number(curr_num):
    global cnt
    if curr_num >= n:
        if curr_num == n:
            cnt += 1
            # print(ans)
            final.append(ans)
        return
    
    for i in range(1, 5):
        for j in range(i):
            ans.append(i)

        beautiful_number(curr_num+i)

        for j in range(i):
            ans.pop()

    return cnt

print(beautiful_number(0))
print(final)

2. final에 ans를 복사해서 붙여넣기 -> 이러면 가능! 

n = int(input())
ans = []
final = []

cnt = 0
def beautiful_number(curr_num):
    global cnt
    if curr_num >= n:
        if curr_num == n:
            cnt += 1
            # print(ans)
            final.append(ans[:])
        return
    
    for i in range(1, 5):
        for j in range(i):
            ans.append(i)

        beautiful_number(curr_num+i)

        for j in range(i):
            ans.pop()

    return cnt

print(beautiful_number(0))
print(final)

 

 

대체 왜 이런걸까?

1번 코드 같은 경우에는 final에 ans를 그냥 바로 append 했다. 이럴 경우 final에는 ans 리스트의 주소값이 담김.

for i in range(len(final)):
    print(id(final[i]))
    
'''
22995983695680
22995983695680
22995983695680
22995983695680
'''

 

이렇게 모두 같은 주소 값이 담긴다!

같은 주소값인데 재귀함수를 탈출해서 print하니까 이미 ans 안의 요소들은 다 pop되고 빈 리스트만 출력되는 것이다. 

 

반면에 2번 코드 같은 경우에는 final에 ans를 복사해서 append 했다. ans리스트가 복사되어 다른 주소에 저장되고 그 저장된 주소 값이 final에 담기는 것!

for i in range(len(final)):
    print(id(final[i]))
    
'''
22995983695704
22995983695728
22995983695752
22995983695776
'''

 

이렇게 1번과 달리 모두 다른 주소값이 들어가 있다. 

 

따라서 재귀함수 안에서 밖에 있는 리스트에 저장되고 다시 삭제되는 값들을 재귀함수 밖에서 사용하려면

그 순간의 list 를 복사해서 저장을 해두면 된다.