안녕하세요! 이번 강좌에서는 C#을 이용하여 연결 요소의 개수를 구하는 알고리즘 문제에 대해 자세히 살펴보도록 하겠습니다. 이 문제는 그래프 이론을 기반으로 하며, 연결 요소란 그래프 내에서 서로 연결된 정점들의 집합을 의미합니다. 이 강좌를 통해 문제를 해결하기 위한 알고리즘적 사고와 C# 프로그래밍 스킬을 향상시킬 수 있을 것입니다.
문제 설명
그래프 G가 주어질 때, G의 연결 요소의 개수를 구하는 프로그램을 작성하시오. 그래프는 정점 수 N과 간선 수 M으로 정의되며, 각 간선은 두 개의 정점을 연결합니다.
입력 형식: - 첫째 줄에는 정점의 개수 N (1 ≤ N ≤ 1000)과 간선의 개수 M (0 ≤ M ≤ 100,000)이 주어진다. - 다음 M줄에는 간선의 양끝 정점 번호 u와 v (1 ≤ u, v ≤ N)가 주어진다. 출력 형식: - 첫째 줄에 연결 요소의 개수를 출력한다.
예제
입력: 6 5 1 2 2 3 4 5 출력: 3
이 예제에서는 정점 1, 2, 3이 연결 요소를 이루고 있고, 정점 4와 5가 또 다른 연결 요소를 형성하고 있으며, 정점 6은 연결된 간선이 없으므로, 총 3개의 연결 요소가 존재합니다.
문제 풀이 과정
1단계: 그래프 표현
이 문제를 해결하기 위해서는 그래프를 어떻게 표현할지를 결정해야 합니다. 흔히 사용하는 방법은 인접 리스트나 인접 행렬을 사용하는 것입니다. 인접 리스트를 사용하면 메모리 사용량을 줄일 수 있어 더 효율적입니다. C#에서는 일반적으로 Dictionary나 List를 사용하여 인접 리스트를 구현할 수 있습니다.
List<int>[] graph = new List<int>[N + 1];
for (int i = 1; i <= N; i++)
graph[i] = new List<int>();
2단계: 간선 정보 입력
입력된 간선 정보를 바탕으로 그래프를 구성해야 합니다. 각 간선의 두 정점을 입력받아 서로의 리스트에 추가해 줍니다. 이를 통해 그래프의 구조를 완성할 수 있습니다.
for (int i = 0; i < M; i++)
{
int u = int.Parse(Console.ReadLine());
int v = int.Parse(Console.ReadLine());
graph[u].Add(v);
graph[v].Add(u);
}
3단계: DFS 또는 BFS 구현
연결 요소의 개수를 구하기 위해서는 DFS(깊이 우선 탐색) 또는 BFS(넓이 우선 탐색)를 활용하여 각 정점을 탐색할 필요가 있습니다. 이미 방문한 정점은 다시 방문하지 않도록 관리해야 합니다. 방문 여부를 저장하기 위해 bool 배열을 사용할 수 있습니다.
bool[] visited = new bool[N + 1];
그 다음 DFS 메소드를 구현하여 주어진 정점에서 시작하여 연결된 모든 정점을 방문합니다. 각 DFS 호출이 끝날 때마다 연결 요소의 개수를 증가시킵니다.
void DFS(int node)
{
visited[node] = true;
foreach (var neighbor in graph[node])
{
if (!visited[neighbor])
DFS(neighbor);
}
}
4단계: 전체 알고리즘 구현
마지막으로 연결 요소의 개수를 계산하기 위해 전체 정점을 순회하면서 DFS를 호출하고, 방문하지 않은 정점마다 연결 요소의 개수를 카운트합니다. 최종적으로 연결 요소의 수를 출력합니다.
int count = 0;
for (int i = 1; i <= N; i++)
{
if (!visited[i])
{
DFS(i);
count++;
}
}
Console.WriteLine(count);
전체 코드
위의 단계들을 종합하여 C#으로 작성된 전체 코드는 다음과 같습니다:
using System;
using System.Collections.Generic;
class Program
{
static List<int>[] graph;
static bool[] visited;
static int N, M;
static void Main()
{
var input = Console.ReadLine().Split();
N = int.Parse(input[0]);
M = int.Parse(input[1]);
graph = new List<int>[N + 1];
for (int i = 1; i <= N; i++)
graph[i] = new List<int>();
for (int i = 0; i < M; i++)
{
input = Console.ReadLine().Split();
int u = int.Parse(input[0]);
int v = int.Parse(input[1]);
graph[u].Add(v);
graph[v].Add(u);
}
visited = new bool[N + 1];
int count = 0;
for (int i = 1; i <= N; i++)
{
if (!visited[i])
{
DFS(i);
count++;
}
}
Console.WriteLine(count);
}
static void DFS(int node)
{
visited[node] = true;
foreach (var neighbor in graph[node])
{
if (!visited[neighbor])
DFS(neighbor);
}
}
}
결론
이번 강좌에서는 C# 언어를 활용하여 그래프의 연결 요소 개수를 구하는 문제를 해결했습니다. 그래프 이론에서의 기본적인 DFS/BFS 기술을 통해 문제를 접근하고 해결 방법을 모색하는 과정에서 알고리즘적 사고를 향상시킬 수 있었습니다. 앞으로도 이러한 문제를 많이 풀어보며 실력을 쌓아가시길 바랍니다!
감사합니다!