문제 소개
노드(node)와 간선(edge)으로 이루어진 그래프가 주어집니다. 이 문제의 목표는 어떤 간선에도 연결되지 않은 노드의 최대 개수를 구하는 것입니다. 완전 그래프(complete graph)에서는 노드 수가 항상 간선 수보다 작거나 같다는 성질을 활용하면 됩니다.
핵심 아이디어
노드가 n개인 완전 그래프에는 정확히 n(n-1)/2개의 간선이 존재합니다. 따라서 주어진 간선을 모두 배치하는 데 필요한 최소한의 노드 수를 찾으면, 전체 노드 수에서 그 값을 빼서 남는 노드의 최대 개수를 계산할 수 있습니다.
수식으로 정리하면 다음과 같습니다.
간선 수 = n(n-1)/2 (n은 노드 수)
양변에 2를 곱하면 2 × 간선 수 = n(n-1)이 되며, n(n-1)이 실제 간선 수의 2배를 초과하는 시점부터는 노드가 남게 됩니다. 따라서 i를 1부터 n까지 순회하면서 i(i-1) > 2 × 간선 수가 처음 만족되는 지점을 찾고, 그때의 n - i를 결과로 반환하면 됩니다.
예제로 이해하기
입력 − nodes = 5, edges = 2
출력 − 간선에 포함되지 않는 노드의 최대 개수 − 2
설명 − 2개의 간선을 만들려면 최소 3개, 최대 4개의 노드가 필요합니다. 3개의 노드만 사용할 경우 간선에 연결되지 않은 노드는 최대 2개입니다.
입력 − nodes = 2, edges = 1
출력 − 간선에 포함되지 않는 노드의 최대 개수 − 0
설명 − 하나의 간선을 만들려면 최소 2개의 노드가 필요합니다. 이 경우 두 노드 모두 간선에 사용되므로 남는 노드는 없습니다.
알고리즘 접근 방법
- 사용 가능한 데이터로 변수 nodes(노드 수)와 edges(간선 수)를 받습니다.
- 함수 maximum(int nodes, int edges)는 노드 수와 간선 수를 매개변수로 받아, 그래프에서 어떤 간선에도 속하지 않는 노드의 최대 개수를 반환합니다.
- 변수 i, temp, max를 선언합니다.
- i = 0부터 i <= nodes까지 FOR 반복문을 실행합니다.
- temp = i * (i - 1)을 계산합니다.
- total = 2 * edges를 계산합니다.
- temp가 total보다 크거나 같으면 반복문을 종료(break)합니다.
- max = nodes - i를 계산합니다.
- max를 결과로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int maximum(int nodes, int edges){
int i, temp = 0, max;
for (i = 0; i <= nodes; i++){
temp = i * (i - 1);
int total = 2* edges;
if (temp >= total){
break;
}
}
max = nodes - i;
return max;
}
int main(){
int nodes = 10;
int edges = 5;
cout<<"Maximize number of nodes which are not part of any edge in a Graph are:"<<maximum(nodes, edges) << endl;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
Maximize number of nodes which are not part of any edge in a Graph are: 6
결과 해석: 노드 10개와 간선 5개가 주어졌을 때, 4개의 노드만으로 최대 6개의 간선을 만들 수 있으므로 5개의 간선을 모두 배치하는 데 4개의 노드면 충분합니다. 따라서 남는 노드는 10 - 4 = 6개가 됩니다.