[백준/Python3] 11724번 연결 요소의 개수

문제

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

코드

from sys import stdin, setrecursionlimit
setrecursionlimit(10**7)

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

for i in range(M):
	u, v = map(int, stdin.readline().split())
	graph[u].append(v)
	graph[v].append(u)

visited = [False] * (N + 1)

def DFS(v):
	visited[v] = True
	for i in graph[v]:
		if not visited[i]:
			DFS(i)

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

• 한번 탐색할 때마다 시작한 정점과 연결된 모든 요소를 방문해야 하므로 DFS를 이용해 풀이했다.
• for문을 이용해 정점 중 방문하지 않은 정점이 있다면 시작점으로 선택하고 DFS를 이용해 탐색하면서 연결된 정점을 모두 방문한 것으로 표시한다.

오류

• 정점의 범위가 1~N인데 for문의 범위를 (1, N)으로 잘못 설정하여 N번째 정점이 시작점이 되는 경우 탐색하지 못하는 오류가 있었다.