📝 문제 정보

🤔 나의 아이디어

처음에는 단순히 모든 노드를 순회하면서 연결된 노드들을 찾아 그룹으로 묶으면 되지 않을까 생각했다

그래서 for 루프를 돌면서 각 노드를 시작점으로 DFS나 BFS를 수행하고, 한 번의 탐색이 끝날 때마다 카운트를 1씩 올리는 방식으로 접근했다

방문한 노드는 visited 배열에 표시해서 중복 방문을 피하도록 했다

이 방법으로 모든 노드를 한 번씩만 확인하면서 연결된 덩어리(연결 요소)의 개수를 정확히 셀 수 있을 거라고 생각했다

✨ 소스 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

visited = [False] * (n + 1)
count = 0

def dfs(v):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

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

print(count)

💡 배운 점 & 느낀 점

• DFS/BFS의 기본: 연결된 모든 노드를 탐색하는 DFS/BFS의 핵심 개념을 다시 한번 되새길 수 있었다
• 재귀 깊이: Python에서 DFS를 재귀로 구현할 때, 노드 개수가 많으면 RecursionError가 발생할 수 있다는 점을 배웠다 sys.setrecursionlimit()으로 재귀 깊이를 늘려줘야 한다는 것을 기억해야겠다
• 방문 처리의 중요성: visited 배열을 사용해 방문한 노드를 정확히 체크하는 것이 중복 계산을 막고 알고리즘의 효율성을 보장하는 핵심이라는 것을 깨달았다

TODO

• 시간 복잡도와 공간 복잡도 분석하기
• 다른 사람의 풀이와 비교하며 개선점 찾아보기
• BFS로도 동일한 문제를 풀어보기