현대의 알고리즘 문제풀이에서 그래프는 매우 중요하고 기본적인 데이터 구조입니다. 이 글에서는 그래프의 표현 방식에 대해 설명하고, C++을 사용하여 관련 문제를 해결하는 방법을 배워보겠습니다.
그래프란 무엇인가?
그래프란 정점(vertex)과 간선(edge)으로 구성된 자료구조로, 다양한 관계를 표현하는 데 유용합니다. 예를 들어, 소셜 네트워크에서의 사용자 간의 관계, 도로망에서의 도시 간의 연결, 웹 페이지 간의 링크 등 다양한 상황에서 그래프를 활용할 수 있습니다.
그래프의 표현 방법
그래프는 일반적으로 두 가지 방법으로 표현됩니다: 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)입니다. 각각의 방법은 장단점이 있으므로, 문제의 특성에 따라 적합한 방법을 선택해야 합니다.
1. 인접 행렬
인접 행렬은 2차원 배열을 사용하여 그래프를 표현하는 방법입니다. 행렬의 크기는 V x V(V는 정점의 개수)로, 행렬의 각 원소 (i, j)는 정점 i와 정점 j간의 간선 존재 여부를 나타냅니다.
// C++에서의 인접 행렬 선언
const int MAX = 100; // 최대 정점 수
int adj[MAX][MAX]; // 인접 행렬
int V; // 정점의 개수
인접 행렬의 장점은 특정 간선의 존재 여부를 O(1)로 확인할 수 있다는 점입니다. 그러나 메모리 측면에서는 V의 제곱만큼 사용하므로, 정점 수가 많고 간선 수가 적은 경우 비효율적입니다.
2. 인접 리스트
인접 리스트는 각 정점에 연결된 정점들의 리스트를 사용하는 방법입니다. 이는 간선이 적은 희소 그래프(sparse graph)에 더 적합합니다.
// C++에서의 인접 리스트 선언
#include
#include
using namespace std;
vector adj[MAX]; // 인접 리스트
int V; // 정점의 개수
인접 리스트는 메모리를 좀 더 효율적으로 사용할 수 있으며, 간선 리스트를 순회하는 데 있어 O(E)의 시간이 소요됩니다.
문제: 연결된 컴포넌트 찾기
이 문제에서는 주어진 유향 그래프에서 서로 연결된 모든 컴포넌트를 찾아야 합니다. 즉, 하나의 정점에서 시작해서 도달할 수 있는 정점들의 집합을 찾아내는 것입니다.
문제 설명
정점의 수 V와 간선의 수 E가 주어지고, 각 간선은 두 정점의 쌍으로 주어집니다. 이 그래프에서 연결된 컴포넌트를 모두 찾아 출력하는 프로그램을 작성하세요.
입력 형식
- 첫 번째 줄: 정점의 수 V (1 ≤ V ≤ 1000)
- 두 번째 줄: 간선의 수 E (0 ≤ E ≤ 10000)
- 다음 E 줄: 간선 (u, v) 형태로 주어짐
출력 형식
연결된 컴포넌트의 수와 각 컴포넌트의 정점을 오름차순으로 출력합니다.
문제 풀이 과정
문제를 해결하기 위해 인접 리스트를 사용하여 그래프를 저장하고, 깊이 우선 탐색(DFS)을 통해 연결된 컴포넌트를 찾겠습니다.
1단계: 인접 리스트 구성하기
우선 입력을 받아 인접 리스트를 구성해야 합니다. 정점의 개수와 간선의 수를 입력받고, 각 간선을 통해 관계를 나타내는 리스트를 완성합니다.
2단계: DFS로 연결된 컴포넌트 찾기
탐색이 이루어질 때마다 방문한 정점을 마킹하고, 더 이상 방문할 정점이 없을 때까지 반복하며 컴포넌트를 찾습니다. DFS의 구현은 재귀를 통해 간단히 진행할 수 있습니다.
#include
#include
#include
using namespace std;
vector adj[1001]; // 인접 리스트
bool visited[1001]; // 방문 여부 체크
vector> components; // 연결된 컴포넌트 저장
void dfs(int v, vector &component) {
visited[v] = true; // 방문 체크
component.push_back(v); // 컴포넌트에 추가
for (int u : adj[v]) {
if (!visited[u]) {
dfs(u, component); // 재귀 호출
}
}
}
int main() {
int V, E;
cin >> V >> E;
for (int i = 0; i < E; i++) {
int u, v;
cin >> u >> v; // 간선 입력
adj[u].push_back(v); // 인접 리스트 구성
adj[v].push_back(u); // 무향 그래프임을 가정
}
// 각 정점에 대해 연결된 컴포넌트 찾기
for (int i = 1; i <= V; i++) {
if (!visited[i]) {
vector component;
dfs(i, component); // DFS 탐색
components.push_back(component); // 찾은 컴포넌트 저장
}
}
// 결과 출력
cout << components.size() << "\n"; // 연결된 컴포넌트 수
for (const auto &component : components) {
sort(component.begin(), component.end()); // 컴포넌트 정렬
for (int v : component) {
cout << v << " "; // 정점 출력
}
cout << "\n";
}
return 0;
}
위 코드를 통해 입력된 그래프에서 연결된 컴포넌트를 찾고 출력하는 로직을 구현했습니다. 입력된 그래프의 각 컴포넌트를 오름차순으로 정렬하고 출력하는 방식입니다.
결론
그래프의 표현 방식과 DFS를 통해 문제를 해결하는 과정을 살펴보았습니다. 그래프는 다양한 알고리즘 문제에서 중요한 역할을 하며, 이를 익히는 것은 코딩 테스트에서 좋은 결과를 얻기 위한 기초가 됩니다. 이 강좌를 통해 그래프의 기초적인 이해와 문제 풀이 능력을 향상시키길 바랍니다.