[백준] 15663 N과 M (9) (실버2) / 백트래킹, 파이썬튜터, shallow copy(얕은 복사)

문제요약

나의 코드 및 설명 (실패코드 : 빈 리스트가 출력)

• 처음에는 temp_list에 숫자를 담고 temp_list의 길이(수열의 길이)가 m이 될 때, ans 리스트에 저장된 수열 중 현재의 temp_list의 수열이 없다면 ans에 추가하는 식으로 문제를 풀려고 했다. 그러나 생각과는 다르게 리스트에 아무것도 담기지 않았다.
• 그 이유를 몰랐었는데, 파이썬 튜터라는 사이트를 통해 확인할 수 있었다.
  temp_list의 길이가 m일 때 정상적으로 ans에 append되기는 한다. 그러나 리턴하고 나서 temp_list의 마지막 요소를 pop하면서 방금 전에 ans에 담아놓은 마지막 요소까지 같이 pop된다.
  이유는 잘 모르겠다.ㅠ >> 이유를 찾았다. 바로 shallow copy로 인한 문제이다. temp_list가 리스트 ans 안으로 들어갈 때, temp_list가 직접 들어가는 것처럼 보이지만, 리스트 자체가 들어가는 것이 아니라 리스트의 주소가 들어가기 때문에 temp_list의 요소를 pop하게 되면 ans의 요소도 같이 pop이 되는 것이다. 그러나 추측하자면 같은 함수 내에서 일어난 일이니까 temp_list를 pop하면, ans에도 영향이 가는 것이 아닐까 싶다.. 이래서 넘겨줄 값을 함수의 변수로 지정하여 넘겨주거나 하는 것 같다. 적어도 재귀함수에 있어서 절대적인 것은 없는 것 같다. 앞으로 빈 리스트가 출력할 때는 위와 같이 내가 함부로 pop하지는 않았는지 의심해봐야 될 것 같다.(백트래킹에 지금보다 익숙치 않았을 때는 빈 리스트가 출력되는 경우가 빈번했다..)

def dfs(count):
    if count == m:
        if temp_list not in ans:
            ans.append(temp_list)
            return
    # if count == m:
    #     ans.append(temp_list)
    if count == n:
        return
    
    for i in range(n):
        if visited[i] == 0:
            visited[i] = 1
            temp_list.append(num_list[i])
            dfs(count+1)
            visited[i] = 0
            temp_list.pop()
            
n, m = map(int, input().split())
num_list = list(map(int, input().split()))
num_list.sort()
ans = []
visited = [0] * n
temp_list = []

dfs(0)
print(temp_list)
print(ans)

shallow copy 문제 - 나와 동일한 고민을 한 사람이 남긴 질문에 어떤 천사같은 분이 답변해주셨다.

나의 코드 및 설명 (실패코드 : 시간초과)

• 위와 같이 임시 리스트에 숫자를 담고, 조건을 만족했을 시(수열의 길이가 m) ans에 추가하는 방법이 안먹히니까, 그냥 함수를 호출할 때 넘겨줄 변수(temp_list)를 지정하니까 정상적으로 출력되었다. 하지만 이번엔 시간초과 에러가 났다.
• 왜인지 생각해보았는데, 아마 상위 함수의 종료 조건에서 temp_list가 ans에 이미 존재하는지 확인하는 것이 문제인 것 같다고 생각했다.(시간복잡도를 계산하는 연습이 필요할 것 같다.. ㅠ)

def dfs(count, temp_list):
    if count == m:
        if temp_list not in ans:
            ans.append(temp_list)
        return
    if count == n:
        return

    for i in range(n):
        if visited[i] == 0:
            visited[i] = 1
            dfs(count+1, temp_list+[num_list[i]])
            visited[i] = 0

n, m = map(int ,input().split())
num_list = list(map(int, input().split()))
num_list.sort()
visited = [0] * n
ans = []

dfs(0,[])

for i in ans:
    print(" ".join(map(str, i)))

나의 코드 및 설명 (플래그 활용)

• prev변수를 통해 이전에 담은 수를 변수에 저장해두고, 저장된 변수의 값이 현재 넣을 수(num_list의 요소)가 아니라면 방문하는 방식으로 문제를 해결하였다.
• 함수의 두 번째 변수에 리스트를 넣음으로써 하위 함수를 호출 할 때 리스트에 특정 조건에 해당하는 값을 저장시키고, 리턴할 때는 다시 이전의 함수의 두 번째 변수에 해당하는 리스트를 받는다는 것을 확인할 수 있었다. 말이 조금 어려운데 파이썬 튜터를 통해 확인할 수 있었다.

def dfs(count, temp_list):
    if count == m:
        ans.append(temp_list)
        return
    if count == n:
        return
    
    prev = 0
    for i in range(n):
        if visited[i] == 0 and prev != num_list[i]:
            prev = num_list[i]
            visited[i] = 1
            dfs(count+1, temp_list + [num_list[i]])
            visited[i] = 0

n, m = map(int, input().split())
num_list = list(map(int, input().split()))
num_list.sort()
visited = [0] * n
ans = []

dfs(0, [])
for i in ans:
    print(" ".join(map(str, i)))

1. 하위 함수를 호출 하면서 temp_list에 두 번째 요소 '7'이 저장되고, temp_list = [1,7]이 된다.

2. 리턴하고 돌아오게 되면 이전 함수에서의 temp_list = [1]을 받아서 계속 for문을 돈다.

3. 하위 함수의 for문을 다 돌게 되면 하위 함수를 종료하고 다시 처음의 상위 함수로 돌아와 for문을 수행한다. (temp_list의 첫 번째 요소가 '7'이 된다.)

피드백

동영상 강의를 적지 않게 보았는데도 불구하고, 백트래킹에서 종료 조건에 도달하여 리턴할 때 어떤 순서로 동작하는지 그 흐름에 대해 이해가 잘 되지 않았다.

어떻게 하면 더 잘 이해할 수 있을까 고민하다가 이전에 구매한 코딩테스트 서적에서 소스코드가 실행되는 동안 실제로 메모리에 데이터가 어떻게 부여되는지 시각적으로 볼 수 있는 IDE인 '파이썬 튜터'가 있다는 것이 떠올라 파이썬 튜터를 활용하여 이해하기 위해 노력하였다. 확실히 소스코드 실행 단계별로 메모리에 데이터가 어떻게 부여되는지 볼 수 있으니까 이해도 더 잘할 수 있었다. 앞으로도 이해가 잘 안되는 소스코드가 있다면, 적극적으로 활용해야겠다.