11724 연결 요소의 개수

💡문제 분석 요약

• 방향 없는 그래프에서, "연결 요소"의 개수를 구한다. 연결요소라는 것이 생소했는데, 이는 노드끼리 연결된 묶음의 개수이다.
• 이 말도 이해가 되지 않았지만, 한마디로 DFS가 수행되는 개수를 구하면 된다고 한다.

💡알고리즘 설계

• DFS를 사용하고, 재귀를 이용한다.
• N의 값이 재귀를 고려하면 꽤 크기 때문에, sys.setrecursionlimit(10**7) 이러한 장치를 걸어줘야한다. (나중에 알게됨)

💡코드

import sys
imput = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split()) # 정점개수 n , 간선개수 m
graph = [[False] * (n + 1) for _ in range(n + 1)] # 그래프 선언
visited = [False] * (n + 1)
count = 0 # 연결 요소 개수

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

def DFS(v):
    visited[v] = True
    for i in range(1, n+1):
        if visited[i] == False:
            DFS(i)

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

print(count)

💡시간복잡도

• DFS를 사용하기 때문에 O(N^2)이 될 것으로 보인다.

💡 틀린 이유

• 굉장히 많이 틀렸는데, 일단 재귀 설정때문에 틀렸다. sys.setrecursionlimit(10**7) 이러한 조건을 설정하지 않아서 계속 시간초과나, 런타임 에러가 났다. 기본적으로 체험하는 시간도 굉장히 길었다.
• 연결 요소의 개수가 무엇인지 몰라서 계속 틀렸다. 이는 DFS, BFS가 실행된 횟수를 의미했다. 정확히는, 노드끼리 연결된 묶음의 개수이다.

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

• setrecursionlimit 조건 추가
•  BFS로 푸는 것 연습하기 

💡 느낀점 or 기억할정보

• 재귀를 쓸 때 특히 DFS는 재귀가 어느정도 깊이 빠지는지 문제의 조건을 알고, 제한 여부를 선택해야한다.
• 이런 거 신경 안쓸거면 BFS도 좋다. BFS 풀기를 더 연습해야한다.
• 무방향 그래프 초기화 방법은 저렇게 하는 것인지 체크하기