[BOJ/Python] 11724_ 연결 요소의 개수

문제 출처 : https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

문제

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

입력

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

출력

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

예제 입력 1

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1

2

예제 입력 2

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2

1

---

풀이

 

BFS를 이용하여 연결 요소를 살펴봤다.

 

import sys
import collections
 
def bfs(graph,x,visited):
    count = 0
    queue = collections.deque()
    queue.append(x)
 
    while queue:
        x = queue.popleft()
        if x not in visited:
            count = 1
            visited.append(x)
            queue.extend(graph[x])
    
    return count
 
 
n,m = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
 
for _ in range(m):
    x,y = map(int,sys.stdin.readline().split())
    graph[x].append(y)
    graph[y].append(x)
 
visited=[]
result = 0
 
for i in range(1,n+1):
    result += bfs(graph,i,visited)
 
print(result)

1. 함수부분을 먼저 살펴보면, 탐색할 그래프의 정보가 담겨 있는 graph, 현재 탐색할 노드 x, 방문을 확인할 visited를 매개변수로 설정하였다.
2. bfs구현에 큐를 이용할 것이기때문에 collections모듈을 import하였고, 큐에 현재 탐색할 노드 x를 넣었다.
3. 큐에 데이터가 들어있는동안 while문으로 반복한다.
4. 큐에 있는 데이터를 FIFO로 하나씩 뽑아서 방문했는지를 확인한다.
5. 방문하지 않았다면, 기존의 연결 요소가 아닌 새로운 연결 요소기 때문에 count를 1로 설정해주고, 방문표시를 한다.
6. 그리고 해당 노드와 연결되어있는 노드들의 정보를 큐에 넣어준다.
7. 이 과정을 큐가 빌때까지 반복한다. (최종적으로 연결되어 있는 요소들이 방문표시된다.)
8. count를 return한다. (인자로 받은 x가 이미 방문했던 노드라면, count는 0을 return하고, 아니라면 1을 return한다.)
9. 최종적으로 count의 값이 곧 연결 요소의 개수이고, 이를 출력한다.