정점(vertex)이 n개인 그래프가 주어졌을 때, 해당 그래프의 에지 커버(edge cover)를 계산하는 것이 이번 글의 목표입니다. 에지 커버란 그래프의 모든 정점을 덮을 수 있도록 필요한 최소한의 간선 개수를 찾는 문제를 의미합니다.
예를 들어 정점의 개수 n = 5라고 가정해 보겠습니다.
이때 그래프는 다음과 같습니다.
이 그래프의 에지 커버는 3입니다.
이번에는 n = 8인 또 다른 예를 살펴보겠습니다.
이 그래프의 에지 커버는 4입니다.
예시 입출력
입력: n = 5
출력: 3
입력: n = 8
출력: 4
접근 방법
에지 커버를 구하는 핵심 아이디어는 매우 간단합니다. 하나의 간선(edge)은 최대 두 개의 정점을 동시에 덮을 수 있기 때문에, 필요한 최소 간선의 개수는 전체 정점 수를 2로 나눈 값이 됩니다. 만약 정점 수가 홀수라면 나머지 하나의 정점을 추가로 덮어야 하므로 올림(ceil) 처리를 해주어야 합니다.
- 사용자로부터 정점의 개수를 입력받습니다.
- 정점의 개수를 2.0으로 나눈 뒤, 그 결과의 올림 값을 구합니다.
- 계산된 결과를 반환하고 출력합니다.
알고리즘
시작
1단계 -> 그래프의 에지 커버를 계산하는 함수 선언
int edge(int n)
float val = 0 으로 초기화
val = ceil(n / 2.0) 대입
val 반환
2단계 -> main() 함수에서
int n = 10 설정
edge(n) 호출 후 결과 출력
종료
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
// 에지 커버를 계산하는 함수
int edge(int n) {
float val = 0;
val = ceil(n / 2.0);
return val;
}
int main() {
int n = 10;
cout<<"필요한 최소 간선의 개수 : "<<edge(n);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
필요한 최소 간선의 개수 : 5
정점이 10개일 때 각 간선이 두 개의 정점을 덮을 수 있으므로, 정확히 5개의 간선만으로 모든 정점을 커버할 수 있습니다. 이처럼 에지 커버 문제는 단순히 정점 수를 2로 나누고 올림하는 것만으로도 효율적으로 해결할 수 있습니다.