[백준] 11724번: 연결 요소의 개수 파이썬

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

11724번: 연결 요소의 개수

나만 bfs싫어?

백준 11724번 연결요소의 개수 문제는 dfs, bfs 어느 걸 써도 풀 수있다.

난 bfs로 풀었다.

 

bfs 헷갈린당.

계속 연습하자

풀이

 

일단 입력으로 방향없는 그래프가 주어진다.

간선 의 양 끝점을 받아서 2차원 리스트로 저장합니당.

파이썬 bfs는 큐로 구현합니다.

큐는 시간복잡도를 고려해서 deque 라이브러리를 활용해 구현.

 

그래프를 bfs로 돌면서 연결요소의 개수를 세면되는 간단한 문제입니당.

 

참고로 그래프의 연결요소는.. 아래 그림처럼 나누어진 각각의 그래프 덩어리..이다.

(문제읽고 뭐지 싶어서 검색했다.)

이 그래프의 연결요소는 2개

 

파이썬 코드

from collections import deque
import sys
       
n, m  = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
    u, v  = map(int, sys.stdin.readline().split())
    graph[u].append(v)  # 그래프 간선 정보 추가
    graph[v].append(u)  # 양방향 간선이므로 추가
# 노드별로 방문 정보를 리스트로 표현
visited = [False] * (n+1)
cnt = 0

for i in range(1, n+1):
    if visited[i] == True: 
        continue
    # 큐 구현을 위한 deque 라이브러리 활용
    queue = deque([i])
    # 현재 노드를 방문 처리
    visited[i] = True
    
    # 큐가 완전히 빌 때까지 반복
    while queue:
        # 큐에 삽입된 순서대로 노드 하나 꺼내기
        v = queue.popleft()
        # 탐색 순서 출력
        # 현재 처리 중인 노드에서 방문하지 않은 인접 노드를 모두 큐에 삽입
        for neighbor in graph[v]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True
    cnt+= 1
print(cnt)