[백준] 연결 요소의 개수(11724번)

[출처] https://www.acmicpc.net/

알고리즘 분류:그래프 이론,그래프 탐색

문제

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

입력

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

출력

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

예제 입출력

접근

이 문제는 단순한 그래프 탐색문제이다
문제에서도 그래프라고 주어져있다.

연결 요소를 구하라는 그래프가 몇개 있냐를 물어보는 것이다.

접근 아이디어는 다음과 같다.

1. 전체노드를 리스트에 넣는다.(주어진 모든 노드를 탐색했는지 확인하기 위해서)
2. 시작노드(전체 노드중에서 임의로 선택함 - 이 풀이에서는 전체노드리스트에서 첫번째요소 선택)부터 bfs 탐색을 실행함.
3. 탐색이 끝나면 연결되어있는 노드들의 정보가 리스트에 담겨서 반환된다.
4. 전체노드 리스트에서 반환된 리스트를 빼주고(집합 자료형을 이용) 연결요소 수(시작은 0)를 +1한다.
5. 전체노드 리스트가 남아있으면 2번부터 반복하고, 남아있지 않다면 연결요소의 수를 반환한다.

코드는 다음과 같다.

import sys
from collections import deque


#n:정점의 개수, m:간선의 개수
n,m = map(int, sys.stdin.readline().split())

#그래프 정보를 담을 리스트 - 인덱스를 1번부터 쓰기 위해서 n+1개로 만듦
graph = {node : list() for node in range(1,n+1)}

#탐색한 노드 표시를 위한 리스트
node_info = list(graph.keys())

#간선정보
for _ in range(m):
    a,b = map(int,sys.stdin.readline().split())

    graph[a].append(b)
    graph[b].append(a)

#bfs 함수 정의
def bfs(start_node,graph):

    visited = dict()

    need_visited = deque(list())

    need_visited.append(start_node)

    while need_visited:

        current_node = need_visited.popleft()

        if current_node not in visited:
            visited[current_node] = 1
            need_visited.extend(graph[current_node])

    return set(visited.keys())

#연결요소 개수 측정
count=0

#전체 노드 리스트를 다 탐색할때까지 반복
while node_info:
    result = bfs(node_info[0],graph)

    #탐색한 노드들을 전체 노드 정보에서 빼고 다시 노드에 넣음
    node_info = list(set(node_info) - result)

    #연결요소의 갯수를 +1함
    count +=1

print(count)

결과

그래프 탐색방법(bfs/dfs)을 알고있으면 크게 어려울것 없는 문제였다.