📌 구해야 하는 정답

방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하는 프로그램을 구하세요

📌 풀이 하기

1️⃣ 연결 요소의 개수 구하기

문제에서 설명이 좀 불친절하지만…

연결 요소의 개념은 아래와 같습니다.

무방향 그래프 내에서 다음 두 조건을 만족하는 정점들의 최대 집합

쉽게 풀어서 이야기하면, 그래프 내에서 연결되어 있는 정점들을 한 그룹으로 묶으면 이게 바로 연결 요소입니다.

연결 요소의 개수는 DFS/BFS로 구할 수 있습니다.

한 정점에서 시작해 연결된 정점들을 재귀적으로 탐색합니다.

이 탐색 과정에서 만나게 되는 모든 정점들을 한 집합에 넣으면 이것이 바로 연결요소입니다.

이 문제에서는 연결요소의 개수만 구하면 되기 때문에 , 연결요소로 탐색된 곳은 True로 체크해 주는 방식으로 탐색하겠습니다.

def dfs(node):
    visited[node] = True
    for x in graph[node]:
        if not visited[x]:
            dfs(x)

여타 다른 그래프 탐색 문제들과 같은 개념으로,

1 ~N까지의 정점들을 탐색합니다.

이 중 탐색이 이루어지지 않은 정점이 있다면, 새로운 연결요소이기 때문에 이 정점에서 dfs 탐색을 시작합니다.