[백준] 11724번 연결 요소의 개수 : 파이썬(python) 설명

 

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

1697번: 숨바꼭질

Hint

X

 

Solution

저는 bfs 알고리즘을 활용하여 해결했습니다.

from collections import deque
N,M = map(int,input().split())
graph=dict()
for i in range(M):
    a,b = map(int,input().split())
    if a not in graph:
        graph[a]=[b]
    else:
        graph[a]+=[b]
    if b not in graph:
        graph[b]=[a]
    else:
        graph[b]+=[a]
    
visit_list=[0]*(N+1)

def bfs(v):
    q=deque()
    q.append(v)
    visit_list[v]=1
    while q:
        v=q.popleft()
        for a in graph[v]:
            if visit_list[a]==0:
                q.append(a)
                visit_list[a]=1
    return True
count=0

for i in graph.keys():
    if visit_list[i]==0:
        if bfs(i) is True:
            count+=1
count+=visit_list.count(0)-1

print(count)

graph를 dict 자료형으로 정리해줍니다

그래야 이후 graph 활용이 수월해집니다.

graph에는 정점에 연결된 간선에 점들을 리스트로 저장합니다.

즉, 예제 1을 기준으로는

1: [2,5] 2: [1,5] 등 이런 식으로 저장합니다.

 

bfs 함수는 정점에 방문처리를 하며정점에 연결된 다른 점들을 q에 넣고

해당 점들에 연결된 점들을 계속 확인하는

너비 우선 탐색 방식의 함수입니다.

 

그리고 graph.keys()를 통해정점 개수를 파악한 이후

bfs를 통해 연결 요소가 얼마나 있는지 파악할 수 있습니다.

 

34번 Line에 visit_list.count(0)-1을

해준 이유는 연결 점이 없는 정점들도 포함해주기 위함입니다.