[BOJ] 15654 : N과 M (5) [백트랙킹](Python)

문제 링크

https://www.acmicpc.net/problem/15654

15654번: N과 M (5)

소스 코드

n,m = map(int,input().split())
nums = sorted(list(map(int,input().split()))) # 정렬 필수

answers = []
sequence = []
def permutation():
    if len(sequence) == m: # m개를 다 뽑았으면
        answers.append(sequence[:]) # 복사!!
        return

    for idx in range(n): # 숫자를 계속 추가
        if nums[idx] not in sequence:
            sequence.append(nums[idx])
            permutation()
            sequence.pop() # 끝 숫자 제거
permutation()
for answer in answers:
    print(*answer,sep=' ')

 

해설

• 백트랙킹
• 리스트

사실 permutation 이라고 구현한 함수의 로직은 아주 간단합니다.

하지만 완성된 숫자 조합을 정답 리스트에 추가하는 과정에서 이해할 수 없는 현상이 나타났습니다.

if len(sequence) == m: # m개를 다 뽑았으면
    answers.append(sequence)
    return

위 코드 블록은 sequence라는 리스트의 길이가 m이 되면 결과를 저장하도록 하는 함수입니다.

그런데 실제로 answer를 출력해보니 죄다 공백 리스트만 저장되어 있었습니다.

 

너무 이상해서 answer.append 직전에 sequence를 찍어보니 숫자 조합이 제대로 구성되어 있습니다.

예를 들어 nums = [1, 2, 3, 4], m = 3인 경우 종료조건을 만족하는 최초의 sequence는 [1, 2, 3] 이 됩니다.

그래서 이를 출력하면 [1, 2, 3] 이 되지만 answer = [ [ ] ] 였다는 뜻입니다.

 

이 문제는 아래처럼 리스트를 복사해 추가하는 방식으로 해결할 수 있었습니다.

if len(sequence) == m: # m개를 다 뽑았으면
    answers.append(sequence[:]) # 복사!!
    return

리스트에 저장되는 것은 실제 어떤 값이 아니라 메모리 주소입니다.

따라서 재귀 함수 내에 동일한 sequence라는 변수가 반복적으로 추가될 때 같은 메모리 주소를 공유하고 있기 때문에 이전에 추가한 리스트의 값도 변하게 된 것입니다.

 

이게 이해되지 않아 같은 현상을 겪은 다른 분의 예시 코드를 가져와봤습니다.

test_list = []
test = [0,0,0]
i = 1
while i <= 3:
    test[1] = i
    print(test)
    test_list.append(test)
    i = i+1
print(test_list)

test[1] 은 test의 두 번째 값을 의미하므로, 이 분이 의도하신 것은 [0, 1, 0], [0, 2, 0], [0, 3, 0] 을 각각 추가하는 것이었습니다.

그러나 실제로는 [0, 3, 0], [0, 3, 0], [0, 3, 0] 이 출력됩니다.

이는 test라는 동일한 메모리 주소를 가지는 변수에 값만 바뀌게 되면서 마지막으로 업데이트 된 값을 기준으로 리스트가 추가되었기 때문입니다.

 

저도 이전에 코딩 테스트를 보면서 이 구조를 이해하지 못해 논리는 알겠는데 정답을 return하지 못한 적이 있었습니다.

단순히 출력만 해도 정답이 되는 BOJ 시스템과 다를 수 있다는 점을 인지하고 가는 것이 중요하겠습니다 !!