[백준][11724] 연결 요소의 개수 | 파이썬

👉 문제 분석

방향 없는 그래프가 주어졌을 때, 연결 요소개수 구하기

👉 알고리즘 설계

dfs를 사용하였다.

 

👉 코드

import sys
from collections import defaultdict

def dfs(x):
    visited[x] = True

    for node in graph[x]:
        if not visited[node]:
            dfs(node)

sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m = map(int, input().split())
graph = list([] for _ in range(n+1))

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False]*(n+1)
cnt = 0 #연결 요소 개수

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

print(cnt)

 

👉 틀린 이유
런타임 에러

 

👉 틀린 부분 수정 or 다른 풀이

from collections import defaultdict

sys.setrecursionlimit(10**6)

를 사용하였다.

 

👉 느낀점 or 기억할정보

1. 연결 요소란, 노드끼리 연결되어 있는 묶음의 개수이다.
2. 대부분이 파이썬의 재귀 최대 깊이의 기본 설정이 1,000회  으로 매우 얕은 편이다. 그리고 런타임 에러가 발생하는 경우가 있다. 이때, 코드의 상단에 sys.setrecursionlimit(10**6)을 작성해주면 재귀의 최대 깊이가 10**6으로 바뀌게 된다.