bj11724 연결요소의 개수

이 문제는 DFS, BFS 둘다 풀 수 있는 문제!

📌우선 그래프 문제임을 확인해서 DFS로 할건지 BFS로 할 건지 고민했다.
그래서 그냥 재귀함수 구조로 DFS로 풀었음

📌visit = [False] * (n+1) 을 True 로 바꿔주면서 만약 True이면 더 이상 탐색하지 않도록 했고, 모든 node에 대해서 DFS로 check를 할 필요가 있었음! 최악의 경우 모든 노드가 연결되어 있지 않을 수 있으니까!

그러면서 DFS를 호출한 횟수만 세어주면 문제 해결 완료!

📍 첫 오답.
runtime error - recursion error가 발생함...
나는 진짜 완전 잘 했는데 에러 뜨길래 error 메시지로 구글링을 해봄..
최대 재귀 호출 횟수를 초과했다는 것을 알게되었고
그래서 이를 해결하기 위해서 한 가지 방법을 알게 되었고
다른 하나는 내가 재귀적으로 호출하는 것이 아니라 코드를 아예 수정해서 만들었음!

재귀로 푸는 해결법!
최대 재귀 횟수를 늘려주면 됨!

sys.setrecursionlimit(10000)

import sys
sys.setrecursionlimit(10000)

n, m = map(int, sys.stdin.readline().split())
card = [[] for _ in range(n+1)]
@@ -11,13 +10,24 @@
visit = [False] * (n+1)


# def dfs(graph, start):
#     if start == n+1:
#         return
#     visit[start] = True
#     for i in graph[start]:
#         if not visit[i]:
#             dfs(graph, i)


def dfs(graph, start):
    stack = [start]
    visit[start] = True
    for i in graph[start]:
        if not visit[i]:
            dfs(graph, i)
    while stack:
        v = stack.pop()
        for i in graph[v]:
            if not visit[i]:
                stack.append(i)
                visit[i] = True


cnt = 0
for i in range(1, n+1):
    if not visit[i]:
        cnt += 1
        dfs(card, i)
print(cnt)

재귀가 아닌 내가 고안한 해결법
아예 그냥 반복문으로 stack을 빼는 것으로 구현했음!

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

visit = [False] * (n+1)


# def dfs(graph, start):
#     if start == n+1:
#         return
#     visit[start] = True
#     for i in graph[start]:
#         if not visit[i]:
#             dfs(graph, i)


def dfs(graph, start):
    stack = [start]
    visit[start] = True
    while stack:
        v = stack.pop()
        for i in graph[v]:
            if not visit[i]:
                stack.append(i)
                visit[i] = True


cnt = 0
for i in range(1, n+1):
    if not visit[i]:
        cnt += 1
        dfs(card, i)
print(cnt)