백준 11724번 연결 요소의 개수 (너비 우선 탐색 BFS)

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력

6 5

1 2

2 5

5 1

3 4

4 6

예제 출력 

2

---

풀이

백준 2667번 단지 번호 붙이기 (너비 우선 탐색 BFS)

백준 1012번 유기농 배추 (너비 우선 탐색 BFS)

 

위 두 문제와 비슷한 유형의 문제이다. 서로 연결되어 있는 꼭짓점들은 그래프를 이루고, 그 그래프는 다른 그래프들과 이어져있을 수도, 아닐 수도 있다. 각각 독립된 그래프가 몇 개인지를 찾는 문제이다.

 

시간을 최대한 줄이기 위해 O(V)를 이용해 부모까지 저장하는 기존의 BFS대신 간소화된 BFS를 사용했다. 또한 queue를 list대신 deque를 이용했기에 popleft()에서도 O(n)을 O(1)로 아낄 수 있었다.

 

추가로, input() 대신 sys.stdin.readline()을 이용하면, 여러 줄의 입력을 읽을 때 시간을 좀 더 아낄 수 있다고 한다.

 

import sys
from collections import deque
 
def bfs(graph, start_node):
    visit = list()
    queue = deque()
 
    queue.append(start_node)
 
    while queue:
         node = queue.popleft()
         if node not in visit:
             visit.append(node)
             queue.extend(graph[node])
    return visit
 
data = dict()
N, M = map(int, sys.stdin.readline().split())
 
for i in range(N):
    data[str(i+1)] = []
 
for i in range(M):
    u, v = sys.stdin.readline().split()
    data[u].append(v)
    data[v].append(u)
    
answer = []
keys = set()
 
for i in range(N):
    if str(i+1) not in keys:
        temp = bfs(data, str(i+1))
        answer.append(temp)
        keys.update(temp)
 
print(len(answer))