백준 - 연결 요소의 개수(파이썬)

📃 문제

💟 코드

BFS방법으로 문제를 해결했다..!! 오랜만의 BFS라...조금 오래 걸렸다ㅠㅠ

# 백준 11724 연결 요소의 개수

# BFS 활용
import sys
from collections import deque

def check(n):
    visited[n] = 1
    Q = deque([n])
    while Q:
        a = Q.popleft()
        for i in arr[a]:
            if not visited[i]:
                visited[i] = 1
                Q.append(i)   

N, M = map(int, sys.stdin.readline().split())
arr = [[] for _ in range(N+1)]
visited = [0]*(N+1)
for _ in range(M):
    u, v = map(int,sys.stdin.readline().split())
    arr[u].append(v)
    arr[v].append(u)
result = 0
for i in range(1,N+1):
    if not visited[i]:
        check(i)
        result += 1
print(result)

✨ 코드 풀이

간선으로 연결되어있는 각각의 정점을 각 정점의 리스트 안에 넣어주는 작업을 먼저 해주었다.
그리고 이미 사용한 정점도 체크해주어야 하기 때문에 visited를 만들어 체크할 수 있게 해주었고, check라는 함수를 만들어 visited가 0이면 해당 정점을 지나갈 수 있게 했다.
그렇게 연결된 모든 정점을 지나게 되면 함수가 끝나고, result에 1을 더하게 해 연결되어있는 요소가 몇개인지 알 수 있다!