[백준] 32301 세계를 만들어요 (C++)

문제

원문 링크 : https://www.acmicpc.net/problem/32301

호반우는 세계를 부수고, 세계를 창조한다.

오늘도 호반우는 무방향 그래프로 이루어진 세계를 부숴버려 세계는 간선 없이 $1$번부터 $3N$번까지 번호가 매겨진 정점 $3N$개만 남게 되었다.

호반우는 $3M$개의 간선을 만들어 세계를 다시 창조하려 하는데 각 정점에 연결된 간선의 개수가 소수이고 모든 정점이 연결되게 하려 한다. 임의의 두 정점이 이미 간선으로 연결되어 있다면 간선을 연결할 수 없으며 같은 정점 $2$개를 잇는 간선인 루프가 생기면 안 된다.

호반우를 도와 세계를 만들어보자.

풀이 및 구현

문제를 풀기 위해선 약간의 관찰이 필요하다.

우선 간선 하나가 두 정점을 이으므로 하나의 간선이 생길 때마다 각 정점에 연결된 간선의 총합은 2씩 증가한다.

또한 M의 범위가 $N \leq M \leq 2N$ 이다.

만약 $N == 4$일 때 $M == N$이라면 정점의 개수는 12개, 간선의 개수는 12개가 나온다.

각 정점에 연결된 간선의 총합은 간선의 개수 * 2이므로 24가 되고 이를 정점의 개수로 나누면 정점당 평균 2개의 간선이 연결되야한다.

이는 아래 그림과 같이 연결하면 된다.

사이클을 이루게 한줄로 구성하면 정점당 2개의 간선이 연결되므로 소수를 유지할 수 있다.

만약 $M == 2N$이면 정점의 개수는 12개, 간선의 개수는 24개가 나온다.

각 정점에 연결된 간선의 총합은 48이고 이를 정점의 개수로 나누면 정점당 평균 4개의 간선이 연결되야하지만 4는 소수가 아니기 때문에 6개의 정점은 간선이 3개 연결되고, 6개의 정점은 간선이 5개 연결되면 이를 해결할 수 있다.

$N$이 홀수인 경우는 계산이 살짝 다르겠지만, 결국 하나의 정점에 연결되는 간선의 수가 최대 5개이기 때문에, 각 정점에 연결된 간선을 2, 3, 5개로 잘 유지만 한다면 1 2를 제외한 모든 경우에서 소수를 유지할 수 있다.

그러면 어떻게 연결해서 소수를 유지할 수 있게 만들지 생각하면 된다.

정점을 아래처럼 6개씩 묶어 주면 쉽게 해결할 수 있다.

정점이 6개 있을 때 제일 먼저 3칸씩 떨어진 정점들을 이어준다. (1 - 4, 2 - 5, 3 - 6)

그러면 각 정점당 연결된 간선의 개수는 3개가 된다.

ans.push_back({i * 3, (i + 1) * 3});
ans.push_back({i * 3 + 1, (i + 1) * 3 + 1});
ans.push_back({i * 3 + 2, (i + 1) * 3 + 2});

그 다음 2칸씩 떨어진 정점 3개를 서로 이어준다. (1 - 3, 1 - 5, 3 - 5)

그러면 1, 3, 5번째 정점에 연결된 간선의 개수는 5개, 나머지는 3개이다.

ans.push_back({i * 3, i * 3 + 2});
ans.push_back({i * 3, (i + 1) * 3 + 1});
ans.push_back({i * 3 + 2, (i + 1) * 3 + 1});

또 다른 2칸씩 떨어진 정점 3개를 묶어 서로 이어준다. (2 - 4, 2 - 6, 4 - 6)

그러면 6개의 정점 모두 5개의 간선이 연결된다.

ans.push_back({i * 3 + 1, (i + 1) * 3});
ans.push_back({i * 3 + 1, (i + 1) * 3 + 2});
ans.push_back({(i + 1) * 3, (i + 1) * 3 + 2});

이 방법을 이용하여 간선의 개수를 $N$부터 시작해 $M$이 될 때까지 이를 반복하면 소수를 유지할 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M; cin >> N >> M;
    if (N == 1 && M == 2) {
        cout << "NO";
        return 0;
    }
    cout << "YES\n";
    vector<array<int, 2>> ans;
    ans.reserve(3 * M);

    for (int i = 0; i < 3 * N; i++) {
        ans.push_back({i, (i + 1) % (3 * N)});
    }

    int step = 0, i = 0;
    while ((int)ans.size() < 3 * M) {
        if (!step) {
            ans.push_back({i * 3, (i + 1) * 3});
            ans.push_back({i * 3 + 1, (i + 1) * 3 + 1});
            ans.push_back({i * 3 + 2, (i + 1) * 3 + 2});
            step++;
        }
        else if (step == 1) {
            ans.push_back({i * 3, i * 3 + 2});
            ans.push_back({i * 3, (i + 1) * 3 + 1});
            ans.push_back({i * 3 + 2, (i + 1) * 3 + 1});
            step++;
        }
        else {
            ans.push_back({i * 3 + 1, (i + 1) * 3});
            ans.push_back({i * 3 + 1, (i + 1) * 3 + 2});
            ans.push_back({(i + 1) * 3, (i + 1) * 3 + 2});
            i += 2; step = 0;
        }
    }
    for (auto&[s, e] : ans) cout << s + 1 << ' ' << e + 1 << '\n';
}

후기

한 정점에 5개까지만 연결해도 되는 것을 아는 것이 중요한 것 같다.

처음에는 6개의 정점마다 간선을 6개만 연결해서 홀수인 경우 약간의 예외처리가 필요했었는데 글을 쓰면서 정점마다 9개까지 할 수 있는 것이 보여서 다시 풀었다

처음 푼 방식은 아래에 남겨놓았다.

코드 보기

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M; cin >> N >> M;
    if (N == 1 && M == 2) {
        cout << "NO";
        return 0;
    }
    cout << "YES\n";
    vector<array<int, 2>> ans;
    ans.reserve(3 * M);

    for (int i = 0; i < 3 * N; i++) {
        ans.push_back({i, (i + 1) % (3 * N)});
    }

    int step = 0, i = 0;
    while ((int)ans.size() < 3 * M) {
        if (i == N - 1) {
            ans.push_back({i * 3, (i - 1) * 3});
            ans.push_back({(i - 1) * 3, (i - 1) * 3 + 2});
            ans.push_back({(i - 1) * 3 + 2, i * 3 + 2});
        }
        else if (!step) {
            ans.push_back({i * 3, (i + 1) * 3});
            ans.push_back({i * 3 + 1, (i + 1) * 3 + 1});
            ans.push_back({i * 3 + 2, (i + 1) * 3 + 2});
            step ^= 1;
        }
        else {
            ans.push_back({i * 3, i * 3 + 2});
            ans.push_back({i * 3, (i + 1) * 3 + 1});
            ans.push_back({i * 3 + 2, (i + 1) * 3 + 1});
            step ^= 1;
            i += 2;
        }

    }
    for (auto&[s, e] : ans) cout << s + 1 << ' ' << e + 1 << '\n';

}