[백준/Python] 11724번 연결 요소의 개수 구하기

1️⃣문제 설명

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

2️⃣입력

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

3️⃣출력

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

---

👩🏻‍💻작성한 코드

import sys

sys.setrecursionlimit(10 ** 6)  # 재귀 최대 깊이 설정
input = sys.stdin.readline


def DFS(v):
    visited[v] = True
    for i in A[v]:
        if not visited[i]:  
            DFS(i) 


n, m = map(int, input().split())	# 노드 개수, 에지 개수
A = [[] for _ in range(n + 1)]		# 그래프를 인접 리스트로 저장
visited = [False] * (n + 1)		# 방문 기록 저장
cnt = 0					# 연결 요소 개수

for _ in range(m):
    u, v = map(int, input().split())	# 에지의 양끝 점 u, v
    A[u].append(v)
    A[v].append(u)

for i in range(1, n + 1):	
    if not visited[i]:
        cnt += 1
        DFS(i)

print(cnt)

 

💡코드 설명

이 문제는  깊이 우선 탐색(= DFS) 알고리즘을 사용하여 풀었다. 

 

DFS() 함수를 설명하면, 입력 들어온 노드를 visited 리스트에 기록을 해주고, 입력 들어온 노드의 연결 노드 중 방문하지 않은 노드로 DFS()함수를 실행한다 -> 재귀함수 형태 -> 'sys.setrecursionlimit(10 ** 6)' 코드 필요 -> WHY? 파이썬의 재귀 최대 깊이의 기본 설정이 1,000회이기 때문에  재귀를 사용해서 문제를 풀 때 런타임 에러가 발생하는 경우가 대다수

 

for i in range(1, n + 1)인 부분을 보면, n의 개수만큼 반복 했을 때, 방문하지 않은 노드가 있다는 것은 그래프가 연결되어 있지 않다는 것이므로 cnt를 +1 해준다.

 

모든 노드를 탐색하는 데에 실행한 DFS의 실행 횟수 = 연결 요소 개수