[백준, BOJ] 11724 - 연결 요소의 개수

1. Question

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

1.1 Input

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

1.2 Output

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

1.3 Example

입력	출력
6 5 1 2 2 5 5 1 3 4 4 6	2
6 8 1 2 2 5 5 1 3 4 4 6 5 4 2 4 2 3	1

2. Approach

연결요소를 찾는 문제이다. 일반적으로 연결요소를 찾는 방법은 bfs나 dfs로 구성하는 걸로 알려져있다.

하나의 노드로 탐색이 끝나면 순회한 모든 노드는 하나의 연결요소가 된다. 이를 visited 리스트에 기록해두고 순회하지 않은 노드를 다시 탐색한다.

주의할 점은 아무런 연결이 되지 않은 점 노드도 하나의 연결요소가 된다는 것이다.

3. Submission

4. Code

import sys

N, M = map(int, sys.stdin.readline().split())

graph = [[0 for _ in range(N+1)] for _ in range(N+1)]

for _ in range(M):
    raw, col = map(int, sys.stdin.readline().split())
    
    graph[raw][col] = 1
    graph[col][raw] = 1
    
q = []
ans = 0
visited = [0 for _ in range(N+1)]

def bfs(start):
    while len(q):
        cur = q.pop()
        for col in range(1, N+1):
            if graph[cur][col] and visited[col] == 0:
                q.append(col)
                visited[col] = 1

for row in range(1, N+1):
    if visited[row]:
        continue
    
    visited[row] = 1
    q.append(row)
    bfs(row)
    ans += 1
    
print(ans)