💡문제 분석 요약
- 방향 없는 그래프에서, "연결 요소"의 개수를 구한다. 연결요소라는 것이 생소했는데, 이는 노드끼리 연결된 묶음의 개수이다.
- 이 말도 이해가 되지 않았지만, 한마디로 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 풀기를 더 연습해야한다.
- 무방향 그래프 초기화 방법은 저렇게 하는 것인지 체크하기
