[Python] 백준/BOJ 11724번: 연결 요소의 개수 (Silver 2)

💻 Problem

문제 보러 가기

 

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

 

💡 Approach

간선 정보(간선의 양 끝점)를 입력받고 있기 때문에 간선 정보를 가지고 graph를 만들어야 한다.

만든 그래프를 바탕으로 정점 1부터 그래프 탐색을 시작한다.

 

만약 연결 요소가 하나인 그래프라면 첫 탐색에서 모든 정점에 방문 처리가 됐을 것이다.

하지만 연결 요소가 2 이상인 그래프라면 첫 탐색 이후에 방문 처리가 되지 않은 정점이 있을 것이다.

그렇게 방문 처리 되지 않은 정점을 찾아서 해당 정점을 기준으로 그래프 탐색을 하는 것을 반복하여 그래프 탐색을 몇 번했는지 세면 된다.

 

아래는 연결 요소에 대한 이해를 돕기 위한 필기이다.

순서대로 백준에서 예제 입력 1, 예제 입력 2를 바탕으로 그렸다.

연결 요소의 개수

 

✏️ Solution

import sys
input = sys.stdin.readline

def dfs(v):
    # 현재 노드를 방문 처리
    visited[v] = True

    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
count = 0

# 연결 정보로 그래프 만들기
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

# 방문하지 않은 노드면 탐색 시작
for i in range(1, n + 1):
    if not visited[i]:
        dfs(i)
        count += 1

print(count)

dfs, bfs 모두 풀이 가능하다.

나는 dfs로 풀었다.

 

시간복잡도: O(n + m)

모든 정점과 간선을 한 번씩 방문하므로 둘을 더한 만큼 걸린다.

중첩된 for문이지만 각 노드에서 모든 간선을 반복적으로 확인하는 것이 아니라 독립적으로 탐색하므로 곱셈이 아니라 덧셈이다.