📌 [BOJ] 백준 11724 연결 요소의 개수

📖 문제

📖 예제

📖 풀이

DFS

import sys
sys.setrecursionlimit(10000000)

N, M = map(int, input().split())

graph = [[] for _ in range(N+1)]
for _ in range(M):
  a, b = map(int, sys.stdin.readline().split())
  graph[a] += [b]
  graph[b] += [a]

visited = [0] * (N+1)

def DFS(V):
  visited[V] = 1
  for i in graph[V]:
    if visited[i] == 0:
      visited[i] = 1
      DFS(i)

cnt = 0
for i in range(1, N+1):
  if visited[i] == 0:
    DFS(i)
    cnt += 1

print(cnt)

BFS

from collections import deque
import sys


N, M = map(int, input().split())

graph = [[] for _ in range(N+1)]
for _ in range(M):
  a, b = map(int, sys.stdin.readline().split())
  graph[a] += [b]
  graph[b] += [a]

visited = [0] * (N+1)

def BFS(V):
  visited[V] = 1
  queue = deque()
  queue.append(V)
  while queue:
    a = queue.popleft()
    for i in graph[a]:
      if visited[i] == 0:
        visited[i] = 1
        queue.append(i)

cnt = 0
for i in range(1, N+1):
  if visited[i] == 0:
    BFS(i)
    cnt += 1

print(cnt)

DFS의 경우 재귀함수의 깊이 제한을 설정하는 sys.setrecursionlimit()을 사용하여 깊이를 늘려줘야 error가 발생하지 않는다.