글 읽기 - 파이썬)리스트에 append 함수를 이용하면 답이 이상하게 나옵니다.

boorooksus 4년 전 1

리스트에 append 함수를 사용하여 데이터 저장하면 답이 이상하게 나옵니다.

아래에 있는 코드는 타잔 알고리즘을 통해 SCC를 찾도록 만들었습니다.
코드를 실행하면 정상적으로 작동되고 답도 올바르게 나오지만
코드 43 ~ 45번째 줄
for i in range(e):
    x, y = map(int, stdin.readline().split())
    connection[x] = connection[x] + [y]
여기부분을
for i in range(e):
    x, y = map(int, stdin.readline().split())
    connection[x].append(y)
이렇게 수정할 경우 이상하게 답이 나옵니다.

디버깅을 해보니 connection리스트 내의 x번째 리스트에만 데이터가 삽입되어야하는데 
connection 리스트 안에 있는 모든 리스트에게 데이터가 삽입이되네요.

같은 표현인것 같은데 왜 다르게 나오는지 궁금합니다.

감사합니다.

from sys import stdin, setrecursionlimit
setrecursionlimit(10**9)

v, e = map(int, stdin.readline().split()) 

connection = [[0]] * (v + 1) #노드의 연결 관계 저장
id = 0 #정점의 아이디
d = [0] * (v + 1) #각 정점의 아이디를 저장하는 리스트
stack = [] #스택
finished = [False] * (v + 1) #처리중인지 확인(True이면 처리 완료)
SCC = [] #같은 SCC에 속한 정점 리스트를 저장하는 리스트

def dfs(x):
    global id
    id += 1
    d[x] = id #고유 아이디를 저장
    stack.append(x) #스택에 자기 자신을 삽입

    parent = d[x]
    for i in range(1, len(connection[x])):
        y = connection[x][i]
        #탐색 안된 노드 일 때
        if d[y] == 0:
            parent = min(parent, dfs(y))
        #처리중인 노드 일 때
        elif finished[y] == False:
            parent = min(parent, d[y])

    if parent == d[x]: #부모가 자기 자신일 때
        scc = []
        while(1):
            t = stack[-1]
            stack.pop()
            scc.append(t)
            finished[t] = True
            if t == x:
                break
        SCC.append(scc)

    return parent

#간선 정보 입력
for i in range(e):
    x, y = map(int, stdin.readline().split())
    connection[x] = connection[x] + [y]
    

#SCC 찾기
for i in range(1, v + 1):
    if d[i] == 0:
        dfs(i)

print(len(SCC)) #SCC 개수 출력

#SCC 데이터를 오름차순으로 정렬
for i in range(len(SCC)):
    SCC[i].sort()
SCC.sort()

for i in range(len(SCC)): #SCC에 속한 정점 출력
    print(*SCC[i], end=" -1\n")

wider93 4년 전 1

connection 리스트를 선언할 때 [ 안쪽 리스트] * n 과 같이 선언하셔서 그렇습니다.

우선 아래 적은 두 개의 코드를 실행하고 결과를 비교해 보시기 바랍니다.

결과가 다릅니다. 위쪽 코드에서 원소를 바꾸면 다른 원소들도 바뀝니다. 이유가 뭘까요?

이유는, 애초에 파이썬이 원소를 하나만 만들고 x[i]들의 주소를 전부 똑같이 지정했기 때문입니다.

맞은 코드에서는
connection[x] = connection[x] + [y]

를 선언할 때마다, connection[x]를 새로 계산해서 새로 만듭니다. 그래서 새로 만든 리스트는 다른 인덱스에 있는 리스트들과 값이 달라집니다. 만약

connection[x] += [y]

라고 적었다면 이미 있는 리스트를 바꿔 주는 작업을 하고 새로 만들지는 않으므로, append를 했을 때와 같은 문제가 생길 겁니다.

잘 설명드렸는지 모르겠네요. 이와 같은 이유로 따로 메모리 절약이 필요한 게 아니라면 2차원 배열을 초기화할 때는 곱하기를 사용하지 않는 것이 좋습니다.

# 1
x = [[0, 1]]*4
x[0][0] = 1
print(x)
# 2
x = [[0, 1] for _ in range(4)]
x[0][0] = 1
print(x)

wider93 4년 전 2

위에 적은 것은 정말 대강의 설명이니 더 알고 싶으시다면 immutable과 mutable을 검색해보시기 바랍니다.

가령 리스트나 집합은 mutable 자료형이고, 문자열이나 튜플, 정수는 immutable 자료형입니다.

boorooksus 4년 전 0

말씀대로 리스트를 초기화할때 곱셈을 사용하지 않으니 잘되네요!

덕분에 immutable과 mutable에 대해서 알게되었습니다.

감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬)리스트에 append 함수를 이용하면 답이 이상하게 나옵니다.

boorooksus 4년 전 1

wider93 4년 전 1

wider93 4년 전 2

boorooksus 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말