파이썬 코딩테스트 강좌, 연결 요소의 개수 구하기

안녕하세요, 여러분! 오늘은 코딩 테스트에서 빈번하게 등장하는 문제 중 하나인 “연결 요소의 개수 구하기”에 대해 다뤄보려고 합니다. 이 문제는 주어진 그래프의 연결 요소가 몇 개인지를 구하는 것이며, DFS(Depth-First Search) 또는 BFS(Breadth-First Search)와 같은 그래프 탐색 알고리즘을 통해 해결할 수 있습니다. 이번 강좌를 통해 문제의 이해와 해결 방법을 익혀보도록 하겠습니다.

문제 설명

연결 요소의 개수 구하기 문제는 다음과 같이 정의할 수 있습니다:

그래프가 주어질 때, 이 그래프의 연결 요소의 개수를 구하시오.

입력:
- 첫째 줄에 정점의 개수 N (1 <= N <= 1000)와 간선의 개수 M (0 <= M <= 10000)이 주어진다.
- 둘째 줄부터 M개의 줄에 간선의 정보를 나타내는 두 정수가 주어진다. 두 정수 A, B는 정점 A와 정점 B가 연결되어 있음을 의미한다.

출력:
- 연결 요소의 개수를 출력한다.

문제 접근 방법

그래프 문제를 풀기 위해서는 먼저 그래프의 구조를 이해하는 것이 중요합니다. 우리는 주어진 정점과 간선 정보를 바탕으로 인접 리스트를 구성하여 그래프를 표현할 수 있습니다. 연결 요소는 서로 연결된 정점들의 집합을 의미하며, 이를 찾기 위해 그래프 탐색 알고리즘을 사용합니다. 그래프의 모든 정점을 방문하면서 방문하지 않은 정점을 만날 때마다 새로운 연결 요소가 발견된 것으로 간주할 수 있습니다.

구현 단계

입력으로부터 그래프를 인접 리스트 형태로 구성합니다.
모든 정점을 방문하면서 DFS 또는 BFS를 통해 연결 요소를 탐색합니다.
탐색 과정에서 방문하지 않은 정점을 만날 때마다 연결 요소의 개수를 증가시킵니다.

코드 구현

이제 위 알고리즘을 바탕으로 실제 코드를 작성해보겠습니다. 파이썬 언어로 DFS를 사용하여 연결 요소의 개수를 구할 것입니다.

def dfs(vertex, adjacency_list, visited):
    visited[vertex] = True # 현재 정점을 방문 처리
    for neighbor in adjacency_list[vertex]:
        if not visited[neighbor]:
            dfs(neighbor, adjacency_list, visited)

def count_connected_components(n, edges):
    adjacency_list = [[] for _ in range(n + 1)]
    for a, b in edges:
        adjacency_list[a].append(b)
        adjacency_list[b].append(a)

    visited = [False] * (n + 1)
    component_count = 0

    for vertex in range(1, n + 1):
        if not visited[vertex]:
            component_count += 1  # 새로운 연결 요소 발견
            dfs(vertex, adjacency_list, visited)

    return component_count

# 입력 받기
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]

# 연결 요소의 개수 출력
print(count_connected_components(n, edges))

코드 설명

위 코드를 살펴보면 다음과 같은 과정이 반복됩니다.

우선, 인접 리스트 형태로 그래프를 구성합니다. 이때 n + 1 크기의 리스트를 생성하여 1부터 n까지 인덱스를 사용할 수 있게 합니다.
주어진 간선 정보를 이용하여 양방향 그래프를 구성합니다. 각 정점 A에 대해 연결된 정점 B를 추가하고, B에도 A를 추가하여 양방향성을 갖도록 합니다.
방문 처리 리스트인 visited 배열을 정의합니다. 이는 각 정점이 방문되었는지 여부를 저장합니다.
1부터 n까지의 정점을 하나씩 방문하며, 방문하지 않은 정점이 발견되면 DFS를 호출하여 그 정점과 연결된 모든 정점을 탐색합니다. 이 과정에서 연결 요소의 개수를 증가시킵니다.

복잡도 분석

이번 문제의 시간 복잡도는 O(N + M)입니다. 이때 N은 정점의 수, M은 간선의 수를 의미합니다. DFS 또는 BFS를 수행할 때 정점과 간선을 각각 한 번씩 방문하므로, 이는 그래프 탐색의 일반적인 시간 복잡도입니다. 공간 복잡도 또한 O(N + M)으로 그래프를 인접 리스트로 표현하기 위해 사용되며, 방문 여부를 체크하기 위해 추가적인 배열이 필요합니다.

마무리

지금까지 “연결 요소의 개수 구하기”에 대해 알아보았습니다. 이 문제는 코드 구현뿐만 아니라 그래프의 기본 개념을 이해하는 데 도움을 주며, 다양한 변형 문제로 응용될 수 있습니다. 이 강좌를 통해 그래프에 대한 이해도가 높아지길 바랍니다. 다음 강좌에서도 더 흥미롭고 유용한 알고리즘 문제를 다루겠습니다. 감사합니다.