백준_11724 (연결 요소의 개수_DFS 순회 문제_recursion과 시간초과)

• 링크 : https://www.acmicpc.net/problem/11724

---

문제 파악할 때 메모한 것

여태까지 계속 했던 문제유형이다? DFS
=> 30분컷 했음

• 바로 전 문제와 차이점이 없는거 같긴 한데,
• 그나마 차이점이라 하면 n x m 행렬이 아니고 그래프의 행렬인 n x n행렬로 Basic한 DFS 탐색 문제인듯

---

DFS 중요 체크 사항

• 일단 한번에 풀긴 했는데
• DFS이다 보니까 히든 테스트케이스에서 recursion error가 떴음
  - sys.setrecursionlimit()
• 그리고 시간초과가 떴음
  - sys.stdin.readline()

---

코드

''' 내가 푼 - recursion error와 시간초과 주의! '''
import sys
sys.setrecursionlimit(10**5)

def dfs(n, i, graph, visit):
    visit[i] = True
    
    for j in graph[i]:
        if not visit[j]:
            dfs(n, j, graph, visit)

n, m = map(int, sys.stdin.readline().split())

# 그래프 만들기(이웃노드 리스트 만들기) -> edge로 n x n 형태의 행렬 만든다
graph = [[] for _ in range(n+1)]  # 그래프 노드는 1부터 시작이다!!!!!!
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

visit = [False] * (n+1)          # 그래프 노드는 1부터 시작이다!!!!
cnt = 0

for i in range(1, n+1):          # 그래프 노드는 1부터 시작이다!!!(여기가 젤 중요)
    if not visit[i]:
        dfs(n, i, graph, visit)
        cnt += 1                 # DFS 1회 순회 후 +1 (이 문제의 핵심)
print(cnt)