[백준] 11724. 연결 요소의 개수

연결 요소의 개수

분류

너비 우선 탐색(bfs), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

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

입력

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

출력

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

문제풀이

• 백준 문제의 경우 입력 값이 많은 경우 sys.stdin.readline을 선언하고 시작해준다.
• 해당 문제는 재귀 호출을 사용하므로, 재귀 호출 깊이 제한이 1000으로 걸려있는 python의 특성상 setrecursionlimit(10 ** 6)을 상단에 선언하고 시작해주자!

1. (인접행렬 생성) 정점, 간선 입력값을 통해 인접행렬을 만들어준다.
2. 연결 요소, 중복 확인 배열 생성
3. 정점 길이만큼 돌면서 중복 확인 배열에 값이 없을 경우 dfs 재귀

• 3-1. 연결 요소 +1
• 3-2. 중복 처리(chk[i]를 True로 변경)
• 3-3. dfs 함수 재귀

4. dfs 함수 재귀

• 4-1. 인접행렬에 값이 존재(1)하고 중복되지 않는다면
• 4-2. 중복 처리(chk[nxt]를 True로 변경)
• 4-3. dfs 재귀 반복

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N, M = map(int, input().split())

matrix = [[0] * N for _ in range(N)]

# 1. 인접행렬 생성
for i in range(M):
  i, j = map(lambda x: x - 1, map(int, input().split()))
  matrix[i][j] = matrix[j][i] = 1
 
# 2. 연결 요소, 중복 확인 배열 생성
ans = 0 
chk = [False] * N


# 4. dfs 함수 재귀
def dfs(now): 
  for nxt in range(N):
    if matrix[now][nxt] and not chk[nxt]:
      chk[nxt] = True
      dfs(nxt)

# 3. 정점 길이만큼 돌면서 중복 확인 배열에 값이 없을 경우 dfs 재귀
for i in range(N):
  if not chk[i]:
    ans += 1
    chk[i] = True
    dfs(i)

# 정답 print
print(ans)