백준-24444번(알고리즘 수업 - 너비 우선 탐색 1)-python

백준-24444번(알고리즘 수업 - 너비 우선 탐색 1)-python

2차원 배열을 for문이 아닌 다른 방식으로 생성해볼까 하여

adl=[[] for _ in range(V+1)]

이부분을 아래부분으로

adl=[[]]*(V+1)

바꾸어 문제를 풀었는데 모든 배열이 복사되어 나왔다.

그래서 문제가 무엇인지 검색해보았더니,2차원배열을 *를 이용하여 생성하는것은 얕은 복사가 진행되어 배열 내의 요소들이 같은 객체를 가리키게 된다고 하였다.

다시 말해서,이 방식으로 2차원 배열을 선언하고 요소를 변경하게 되면 다른 요소들의 값도 같이 바뀌는 것이었다.

참고:
https://velog.io/@sjy5386/Python-2%EC%B0%A8%EC%9B%90-%EB%B0%B0%EC%97%B4-%EC%84%A0%EC%96%B8%ED%95%98%EA%B8%B0

from collections import deque
import sys
input = sys.stdin.readline


V,E,R=map(int,input().split())
visited=[0]*(V+1)
adl=[[] for _ in range(V+1)]
cnt=1

for _ in range(E):
    m,n=map(int,input().split())
    adl[m].append(n)
    adl[n].append(m)

for x in adl:
    x.sort()    

def bfs(R):
    global cnt
    a=deque([R])
    visited[R]=cnt
    while a:
        b=a.popleft()
        for i in adl[b]:
            if visited[i]==0:
                cnt+=1
                visited[i]=cnt
                a.append(i)

bfs(R)
for k in visited[1:]:
    print(k)