[Python] 11724번 연결 요소의 개수

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

 

import sys
input = sys.stdin.readline

#3.함수 정의
def bfs(node):
    queue=[node]
    
    while queue:
        curr_node=queue.pop(0)
        visited[curr_node]=True

        for next_node in graph[curr_node]:
            if not visited[next_node]:
                queue.append(next_node)
                visited[next_node]=True

#1.입력받기
N,M=map(int,input().split()) #N:정점/M:간선

graph=[[] for _ in range(N+1)]
for _ in range(M):
    u,v=map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

visited=[False for _ in range(N+1)]

#2.자료형 정의

#4.출력
cnt=0
for i in range(1,N+1):
    if not visited[i]:
        bfs(i)
        cnt+=1
print(cnt)

 

간선들의 입력에 대한 matrix 배열을 만드는게 아닌 간선들이 연결된 정점들만 저장하여 그래프를 구성하면 훨씬 더 간단해진다.