Shallow Copy Issue

백준 1260번 DFS와 BFS를 풀면서 입력을 받을 때 이상했던 점이 있었다.

두 정점 사이의 간선을 입력받을 때, 해당 간선 정보가 전체 리스트에 중복되어 기록되었다.

 

아래는 내가 짰던 코드이다.

n,m,v=map(int,input().split()) #n:정점수,m:간선수,v:시작정점
matrix=[[0]*(n+1)]*(n+1)

for _ in range(m):
    v1,v2=map(int,input().split())
    matrix[v1][v2]=1
    matrix[v2][v1]=1
  
    
'''
#Input
4 5 1
1 2
1 3
1 4
2 4
3 4

#Output
[[0, 1, 1, 1, 1],
 [0, 1, 1, 1, 1],
 [0, 1, 1, 1, 1],
 [0, 1, 1, 1, 1],
 [0, 1, 1, 1, 1]]
 '''

 

이 코드의 문제는 다음 부분에 있었다.

matrix = [[0] * (n + 1)] * (n + 1)

해당 코드가 다음과 같이 동작되는 것이였다.

• 내부 리스트 [0] * (n + 1)가 먼저 생성
• 그 후, 같은 객체를 (n + 1)번 곱해서 참조

즉, 모든 행이 동일한 객체를 참조하기 때문에 한 행을 수정하면 나머지 행들도 동일하게 변경된다.

 

이는 얕은 복사(shallow copy) 문제였다. 

 

matrix를 올바르게 초기화하려면 각 행을 개별적으로 생성해야 하므로 다음과 같이 수정하면 되었다.

matrix = [[0] * (n + 1) for _ in range(n + 1)]