[백준] 11724 - 연결 요소의 개수(python 파이썬)

백준 11724 문제 바로가기

풀이 코드

import sys
sys.setrecursionlimit(10 ** 6)

n, m = map(int, sys.stdin.readline().split())  # n은 노드의 개수, m은 서로 연결된 간선의 개수
graph = [[] * n for _ in range(n + 1)]

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

visited = [0] * (n + 1)
cnt = 0


def dfs(start):
    global cnt
    visited[start] = 1
    for d in graph[start]:
        if visited[d] == 0:
            dfs(d)


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

print(cnt)

저번에 푼 백준 2606번 바이러스 문제와 좀 비슷해보여서 쉽게 푸나 싶었는데 시간 초과 + 런타임 에러 때문에 굉장히 애를 먹었다 ..

시간초과는 input말고 sys로 받아주니 해결이 되었고 런타임 에러는 재귀호출 때문에 sys.setrecursionlimit(10 ** 6)를 붙여주니 해결됐다 !!

회고

확실히 비슷한 문제들을 풀고 나니깐 접근이 좀 쉬워졌는데 dfs알고리즘에서 재귀를 사용하다보니 setrecursionlimit(10 ** 6)을 사용해줘야 할 것 같다. 시간 초과를 방지하기 위해서도 input 대신 sys로 받아줘야 할 것 같다!!!