[BOJ][⚪2][백준#11724] 연결 요소의 개수

문제 출처

BAEKJOON Online Judge #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

출력

2

예제 2

입력

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

출력

1

My Sol

import sys
input = sys.stdin.readline
from collections import deque

def bfs(s):
    global visited
    Q = deque()
    Q.append(s)

    while Q:
        u = Q.popleft()
        for v in links[u]:
            if visited[v]: continue
            visited[v] = 1
            Q.append(v)


V, E = map(int, input().split())
links = [[] for _ in range(V)]
for _ in range(E):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    links[u].append(v)
    links[v].append(u)

visited = [0]*V
cnt = 0
for i in range(V):
    if not visited[i]:
        cnt += 1
        bfs(i)
print(cnt)

bfs와 완전탐색을 이용하여 푸는 문제였다. 완전탐색으로 모든 정점에 대하여 visited에 체크되지 않았다면 방문하지 않은 노드이므로, 해당 노드를 시작으로 연결된 모든 노드를 visited 체크한다. 이 일련의 연결 컴포넌트를 확인하고 cnt를 1 올리는 방식을 반복한다.

결과

맞았습니다!!