문제 링크

바로가기

문제 풀이

PY

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

N, M = map(int, input().split())
graph = [[] for _ in range(1001)]
isVisited = [False] * 1001
answer = 0

for i in range(M):
  x, y = map(int, input().split())
  graph[x].append(y)
  graph[y].append(x)

def dfs(node):
  isVisited[node] = True

  for i in graph[node]:
    if not isVisited[i]:
      dfs(i)
  return

for i in range(1, N + 1):
  if not isVisited[i]:
    dfs(i)
    answer += 1

print(answer)

풀이

DFS의 기본이 되는 문제이다.

재귀 함수를 이용해서 문제를 풀었고,
방문이 되어있지 않을 때 정답을 1씩 더해주었다.

새롭게 배운 점

1. 파이썬에서는 재귀를 할 때 안정적인 계산을 위해 1000번의 제한을 두고 있다. 처음에는 이러한 환경으로 백준에서 런타임 에러가 발생했는데 sys.setrecursionlimit(10000)을 통해 재귀 횟수를 늘려주어 문제를 해결했다.