객체와 변수 그리고 참조

• 이미지 출처: https://junstar92.tistory.com/350

이하 게시글은 백준 문제를 풀며 정리한 글입니다.

1. 개념정리(객체, 변수, 참조)

1.1 객체

Python에서 모든 데이터는 객체 이다.
예컨데, [1, 2] 라는 리스트는 하나의 객체이다.

1.2 변수

변수는 객체를 가리키는 이름이다. 한 마디로 명찰 인 것.

a = [1, 2]

라고 한다면, 변수a는 [1, 2]를 가리키는 명찰

1.3 참조(Reference)

변수를 다른 변수에 아래처럼 할당하는 경우

b = a  # b는 a와 같은 리스트 객체를 참조
b.append(3)
print(a)  # 결과: [1, 2, 3]

실제로는 같은 객체에 대한 참조(주소)가 전달되는 것 즉, 그 둘이 별개의 것이 아님.
따라서,
a와 b는 같은 리스트를 가리키므로, 한쪽에서 수정하는 경우에 다른 쪽도 영향을 받아 수정 됨.

백준 15663번 문제 (Back Track)을 풀면서
아래와 같이 코드를 짜서 틀렸었음

import sys

def main():
    N, M = map(int, sys.stdin.readline().rstrip().split())
    num_list = sorted(list(map(int, sys.stdin.readline().rstrip().split())))
    visited = [False] * N
    combination = []
    combination_list = []

    def back_track(depth):
        if (depth == M) and (combination not in combination_list):
            combination_list.append(combination)
            print(*combination)
            return

        for index in range(len(num_list)):
            if not visited[index]:
                visited[index] = True
                combination.append(num_list[index])
                back_track(depth + 1)
                combination.pop()
                visited[index] = False

    back_track(0)


if __name__ == "__main__":
    main()

이유는
combination_list.append(combination)
이 부분과
(combination not in combination_list)
이 부분에 있었는데
append의 대상이 combination을 참조한 것이었으므로, combination의 값이 바뀌면 combination_list 안의 값도 자동으로 바뀌었기 때문

참조와 mutable한 리스트 객체의 특성 콤보로 이런 사태가 일어남.

2. 리스트는 Mutable 하다.

다들 알고 있는 말이지만, 알아서 어디다 쓰나요? 라고 느낄만큼 매우 가볍게 지나치기 마련인데, 이번 알고리즘 문제를 풀며 set과 list의 활용에 대해 더 깊게 알 수 있었다.

• 변경 가능(Mutable)
  리스트는 변경 가능한(Mutable)한 객체이다. 즉, 생성 후에도 내부의 요소를 추가, 삭제, 수정할 수 있으며 그렇기에 앞선 코드에서 append의 대상으로 참조를 넣은 경우에 참조의 대상이 되는 값이 변경될 때마다 list에 추가된 참조값도 저절로 연동되어 바뀌었던 것!
  아래 코드 참고

  combination = []
  results = []
  
  combination.append(1)
  results.append(combination)  # 여기서 results에는 combination의 참조가 저장됨
  
  combination.append(2)
  print(results)  # 결과: [[1, 2]]

3. 재귀 함수와 리스트의 참조 문제

• 재귀 함수에서는 보통 하나의 리스트를 전역 또는 함수 내부의 변수로 두고서 append/pop을 통하여 상태를 변경하며 모든 경우의 수(조합)을 탐색함 (이번 문제에서)

• 만약 이 리스트를 그대로 저장하게 되면, 같은 객체에 대한 참조가 여러번 저장되는 꼴이기에 나중에 값이 변경되면 이미 저장했던 결과 또한 변경된 값을 갖게 됨.

문제가 발생하는 부분

def backtrack(depth):
    if depth == target:
        if combination not in result_list:
            result_list.append(combination)  # combination의 참조 저장
        return

    for x in some_options:
        combination.append(x)
        backtrack(depth + 1)
        combination.pop()

위 코드에서 result_list에 저장된 combination은 모두 같은 객체를 참조하기에 최종 결과가 올바르게 저장되지 않게 되는 것.

4. 해결방법

• 간단하다. 아래와 같이 불변 객체만 포함 가능 한 set을 사용하여 combination에 대해서 tuple로 바꿔준 뒤에 저장하면 된다.

  • 집한을 사용하는 이유는 중복 체크하기 편해서이고, 핵심은 tuple로 바꿔 참조된 객체 값이 set으로 들어갔을 때 불변 되게끔 하는 것.

• 아래는 정답 코드

  import sys
  
  def main():
      N, M = map(int, sys.stdin.readline().rstrip().split())
      num_list = sorted(list(map(int, sys.stdin.readline().rstrip().split())))
      visited = [False] * N
      combination = []
      combination_set = set()
  
      def back_track(depth):
          if depth == M:
              comb_tuple = tuple(combination)
              if comb_tuple not in combination_set:
                  combination_set.add(comb_tuple)
                  print(*combination)
              return
  
          for index in range(len(num_list)):
              if not visited[index]:
                  visited[index] = True
                  combination.append(num_list[index])
                  back_track(depth + 1)
                  combination.pop()
                  visited[index] = False
  
      back_track(0)
  
  if __name__ == "__main__":
      main()