문제 설명
두 개의 정수 N과 K가 주어집니다. N개의 정점을 가진 무방향 그래프를 구성해야 하며, 이 그래프는 다음 조건들을 모두 만족해야 합니다.
- 그래프는 단순(simple) 그래프이면서 연결(connected)되어 있어야 합니다.
- 정점에는 1부터 N까지 번호가 매겨집니다.
- 그래프의 간선 개수를 M이라 할 때, 간선에는 1부터 M까지 번호가 붙으며 각 간선의 길이는 1입니다. i번째 간선은 정점 U[i]와 V[i]를 연결합니다.
- i < j를 만족하는 정점 쌍 (i, j) 중에서 두 정점 사이의 최단 거리가 정확히 2인 쌍이 정확히 K개 존재해야 합니다.
이러한 그래프가 존재한다면 그래프를 직접 구성하여 출력하고, 존재하지 않는다면 -1을 출력해야 합니다.
예를 들어 입력이 N = 5, K = 3이라면 출력은 다음과 같습니다.
7 1, 2 1, 3 1, 4 1, 5 2, 3 2, 4 2, 5
첫 줄의 7은 간선의 개수(M)를 의미하며, 이후 각 줄은 간선이 연결하는 두 정점의 번호를 나타냅니다.
접근 방법
이 문제의 핵심 아이디어는 별(star) 모양의 그래프에서 출발하는 것입니다. 모든 정점을 중심 정점 1에 연결하면, 정점 2부터 N 사이의 서로 다른 정점 쌍은 모두 중심 정점을 거쳐 이동하게 되므로 최단 거리가 2가 됩니다. 이러한 쌍의 개수는 (N−1)×(N−2)/2개로, 거리가 2인 정점 쌍 개수의 최댓값입니다.
따라서 해결 과정은 다음과 같습니다.
- K가 (N−1)×(N−2)/2보다 큰 경우: 어떤 방법으로도 조건을 만족할 수 없으므로 -1을 출력합니다.
- 그 외의 경우: 먼저 별 모양 그래프를 만든 뒤, 정점 2부터 N 사이에 간선을 추가로 연결합니다. 두 정점이 간선으로 직접 연결되면 두 정점 사이의 거리는 2에서 1로 바뀌므로, 거리가 2인 쌍의 개수가 하나씩 줄어듭니다. 필요한 추가 간선의 개수는 (N−1)×(N−2)/2 − K개이며, 전체 간선의 개수는 (N−1)×(N−2)/2 − K + (N−1)개가 됩니다.
알고리즘 의사 코드
if k > (n - 1) * (n - 2) / 2, then:
print -1
return
print ((n - 1) * (n - 2) / 2 - k + n - 1)
for initialize i := 1, when i < n, update (increase i by 1), do:
print pair (1, i + 1)
count := (n - 1) * (n - 2) / 2 - k
for initialize i := 2, when i <= n, update (increase i by 1), do:
for initialize j := i + 1, when j <= n, update (increase j by 1), do:
if count <= 0, then:
return
print pair (i, j)
(decrease count by 1)
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void solve(int n, int k){
if (k > (n - 1) * (n - 2) / 2){
cout << -1 << endl;
return;
}
cout << (n - 1) * (n - 2) / 2 - k + n - 1 << '\n';
for (int i = 1; i < n; i++){
cout << 1 << ", " << i + 1 << '\n';
}
int count = (n - 1) * (n - 2) / 2 - k;
for (int i = 2; i <= n; i++){
for (int j = i + 1; j <= n; j++){
if (count <= 0){
return;
}
cout << i << ", " << j << '\n';
count--;
}
}
}
int main(){
int N = 5;
int K = 3;
solve(N, K);
}
입력
5, 3
출력
7 1, 2 1, 3 1, 4 1, 5 2, 3 2, 4 2, 5
동작 원리 정리
N = 5, K = 3인 경우를 살펴보면, 거리가 2인 정점 쌍의 최대 개수는 (5−1)×(5−2)/2 = 6개입니다. K = 3이므로 이 중 3개를 줄여야 하며, 따라서 정점 2~5 사이에 간선을 3개 추가합니다. 전체 간선 수는 6 − 3 + 4 = 7개가 되어 출력 결과와 일치하는 것을 확인할 수 있습니다.
이 알고리즘의 시간 복잡도는 O(N²)이며, 구성해야 하는 간선의 수 역시 최대 O(N²) 수준이므로 N이 수천 정도까지는 충분히 빠르게 동작합니다.