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

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (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

✏️문제 탐색하기

주어진 그래프에서 연결 요소의 개수를 구하는 문제.
연결 요소란

• 그래프 내에서 모든 노드가 서로 연결되어 있는 서브 그래프.
• 다른 연결 요소와는 어떠한 간선으로도 연결되지 않음.

주어진 조건:

• 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다.
• 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다.
• 같은 간선은 한 번만 주어지므로 중복 안 됨.

✏️알고리즘 선택

그래프의 연결 요소를 탐색하는 문제로 DFS사용.
간선을 읽어 인접 리스트를 생성하므로 O(M)
DFS는 각 정점과 간선을 한 번씩 탐색하므로 O(N + M)
그래서 전체 시간 복잡도는 O(N + M)

✏️코드 설계하기

1. 정점의 개수 N 과 간선의 개수 M 을 입력받습니다.
2. 간선 정보를 읽어 인접 리스트 형태로 그래프를 생성합니다.
3. 현재 노드 v 에서 출발하여 연결된 모든 노드를 탐색합니다.
4. 방문한 노드는 visited 리스트에 기록해 중복 탐색을 방지합니다.
5. 모든 노드를 확인하며, 방문하지 않은 노드에서 DFS를 호출합니다.
6. DFS 호출 횟수를 count로 기록하며, 이는 연결 요소의 개수를 나타냅니다.
7. count 값을 출력합니다.

✏️시도 회차 수정 사항

1회차

RecursionError 에러가 발생,,
찾아보니 "RecursionError는 재귀와 관련된 에러입니다. 가장 많이 발생하는 이유는 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때입니다." 라고 한다..
BOJ의 채점 서버에서 이 값은 1,000으로 되어 있음
그래서

sys.setrecursionlimit(10**6)

코드를 추가

✏️코드 구현

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

list_ = []

for _ in range(N + 1):
    list_.append([])

for _ in range(M):
    a, b = list(map(int, sys.stdin.readline().split()))
    list_[a].append(b)
    list_[b].append(a)

visited = [False for _ in range(N+1)]
count = 0


def dfs(v):
    visited[v] = True
    for i in list_[v]:
        if visited[i] == False:
            visited[i] = True
            dfs(i)


for i in range(1, N+1):
    if visited[i] == False:
        count += 1
        dfs(i)

print(count)