[python] 백준 11724 : 연결 요소의 개수 (실버 2)

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

문제 자체를 이해하는것이 조금 어려웠다. 방향성이 없는 그래프이기 때문에 (1,2) (1,3) 도 2와 3이 연결된 것이라고 하는 것이다. 문제 풀이는 dfs 로 풀면 된다.

import sys
input = sys.stdin.readline
n , m = map(int,input().split())
edges = [tuple(map(int,input().split())) for _ in range(m)]

visited = [False] * (n+1)
nodes = [[] for _ in range(n+1)]   # [[]] * (n+1) 을 하면 동일한 객체가 생성되기 떄문에 값을 새로 추가하면 모든 배열이 동시에 적용된다.
stack = list()
for u , v in edges:
    nodes[u].append(v)
    nodes[v].append(u)
count = 0
for i in range(1,n+1):
    if not visited[i]:
        count += 1
        stack.append(i)
        visited[i] = True
        while stack:
            for node in nodes[stack.pop()]:
                if not visited[node]:
                    visited[node] = True
                    stack.append(node)

print(count)

해당 문제를 풀면서 몰랐던 점을 하나 알았다.

[[] for _ in range(n+1)] 와 [[] * (n+1)] 의 차이가 뭐야?

 

ChatGPT

[[] for _ in range(n+1)]와 [[] * (n+1)]의 차이를 설명해드릴게요.

차이점 설명

1. 리스트 내포(List Comprehension): [[] for _ in range(n+1)]
   • 이 표현식은 새로운 빈 리스트를 생성하여 각 요소로 추가합니다.
   • 즉, 총 n+1개의 개별적인 빈 리스트가 생성됩니다.
   • 각 빈 리스트는 서로 독립적입니다. 하나의 리스트를 변경해도 다른 리스트에는 영향을 미치지 않습니다.
2. 리스트 곱셈(List Multiplication): [[] * (n+1)]
   • 이 표현식은 하나의 빈 리스트를 n+1번 반복하여 새로운 리스트를 생성합니다.
   • 하지만 [[]] * (n+1)로 작성되었을 때는, 동일한 빈 리스트에 대한 참조가 n+1번 반복됩니다.
   • 즉, n+1개의 리스트가 동일한 객체(빈 리스트)를 참조하게 됩니다. 하나의 리스트를 변경하면 모든 리스트에 영향을 미칩니다.

요약

• [[] for _ in range(n+1)]: 각 요소가 서로 독립적인 빈 리스트입니다.
• [[] * (n+1)]: 모든 요소가 동일한 빈 리스트 객체를 참조합니다.

따라서, 그래프를 표현할 때 각 정점의 인접 리스트를 독립적으로 관리하기 위해서는 [[] for _ in range(n+1)] 방식을 사용하는 것이 올바릅니다.