해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 알고리즘 / 11724번 연결 요소의 개수 - DFS

문제 풀이 

이번 문제는 dfs 또는 bfs로 풀 수 있는 문제인데, dfs로 풀어보도록 하겠습니다. 

각 노드를 생성하고, 간선을 연결하여 graph를 만들어 줍니다. 

그리고 각 노드에 대하여 dfs를 진행하도록 하는데, 각 노드에 방문하였다면 skip합니다.

이때 노드에 방문하지 않고, dfs를 진행하도록 하면 count를 올려줍니다. 

dfs를 진행하면서 각 노드에 대하여 visited[node]에 방문했는지 여부를 설정합니다.  

이 동작을 반복하다보면 count를 구할 수 있게 됩니다. 

전체 코드

import sys
sys.setrecursionlimit(10000)

def dfs(index, V, G):
	V[index] = 1
	for i in range(1, N+1):
		if index == i or V[i] == 1 or G[index][i] == 0:
			continue
		dfs(i, V, G)

MAX = 1001
# 입력
N, M = map(int, input().split(' '))

# 변수 설정
graph = [[0] * (MAX+1) for i in range(MAX+1)]
visited = [0] * (MAX+1)
cnt = 0

for i in range(M):
	u, v = map(int, sys.stdin.readline().split())

	## graph u->v, v->u 설정
	graph[u][v] = 1
	graph[v][u] = 1

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


print(cnt)