문제

https://www.acmicpc.net/problem/11724

나의 코드 (DFS)

"""

"""

from sys import stdin, setrecursionlimit
setrecursionlimit(10000)
input = stdin.readline

n, m = map(int, input().split())
graph = [ [] for _ in range(n+1) ]
visited = [False] * (n+1)
answer = 0

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

def dfs(idx):

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

for idx in range(1, n+1): # 1번부터 차례대로 dfs 탐색
    if not visited[idx]:
        visited[idx] = True
        dfs(idx)
        answer += 1

print(answer)

    

나의 코드 (BFS)

"""

"""

from collections import deque
from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
graph = [ [] for _ in range(n+1) ]
visited = [False] * (n+1)
answer = 0

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

def bfs(v):
    visited[v] = True
    q = deque([v])

    while q:
        node = q.popleft()

        for x in graph[node]:
            if not visited[x]:
                visited[x] = True
                q.append(x)

for idx in range(1, n+1): # 1번부터 차례대로 bfs 탐색
    if not visited[idx]:
        bfs(idx)
        answer += 1

print(answer)

    

설명

DFS, BFS를 활용한 문제

재귀에서 한가지 중요한것이 python은 재귀제한이 걸려있기 때문에 재귀 허용치가 넘어가면 런타임에러를 일으킨다. 때문에 sys.setrecursionlimit(10000) 처럼 작성해야 한다.

참고 자료