백준 2812 - 크게 만들기

문제 설명

사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. 사이클 C는 플레이어가 그린 선분들의 부분집합으로, 다음 조건을 만족한다.

C에 속한 임의의 선분의 한 끝점에서 출발하여 모든 선분을 한 번씩만 지나서 출발점으로 되돌아올 수 있다.

문제는 선분을 여러 개 그리다 보면 사이클이 완성 되었는지의 여부를 판단하기 어려워 이미 사이클이 완성되었음에도 불구하고 게임을 계속 진행하게 될 수 있다는 것이다. 이 문제를 해결하기 위해서 게임의 진행 상황이 주어지면 몇 번째 차례에서 사이클이 완성되었는지, 혹은 아직 게임이 진행 중인지를 판단하는 프로그램을 작성하려 한다.

입력으로 점의 개수 n과 m 번째 차례까지의 게임 진행 상황이 주어지면 사이클이 완성 되었는지를 판단하고, 완성되었다면 몇 번째 차례에서 처음으로 사이클이 완성된 것인지를 출력하는 프로그램을 작성하시오.

https://www.acmicpc.net/problem/20040

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 선분을 하나씩 그어갈 때 사이클이 생기는지 여부를 판단하면 된다.

만약 모든 성분을 그어도 사이클이 생기지 않는다면 0을 중간에 사이클이 생긴다면 해당 차례를 출력하면 된다.

 

이미 완성된 그래프에서 사이클을 판정하는 것이 아니라 하나씩 선분을 만들어 가면서 사이클을 판정해야 한다.

이는 유니온 파인드로 판단할 수 있다.

 

부모를 정하는 기준을 정하고 각 선분을 그으며 최상위 부모가 무엇인지 확인한다.

이때 최상위 부모가 같다면 사이클에 포함되었다고 할 수 있다.

이때 부모를 정하는 기준은 크게 중요하지 않고 일관되기만 하면 된다.

int Find(int a)
{
    if (parent[a] == a) return a;
    return parent[a] = Find(parent[a]);
}

void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);

    if (a != b)
    {
        if (a > b) swap(a, b);
        parent[b] = a;
    }
}

작은 번호가 부모가 되도록 설정하였다.

 

이런 과정을 각 입력마다 처리하면 된다.

for (int i = 0; i < M; i++)
{
    int a, b;
    cin >> a >> b;

    a = Find(a);
    b = Find(b);

    if (a == b)
    {
        cout << i + 1;
        return 0;
    }

    Union(a, b);
}

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
#define MAX 987654321

using namespace std;
int N, M;
vector<int> parent;

int Find(int a)
{
    if (parent[a] == a) return a;
    return parent[a] = Find(parent[a]);
}

void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);

    if (a != b)
    {
        if (a > b) swap(a, b);
        parent[b] = a;
    }
}

int main()
{
    INPUT_OPTIMIZE;

    cin >> N >> M;
    parent.resize(N);

    for (int i = 0; i < N; i++)
    {
        parent[i] = i;
    }

    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;

        a = Find(a);
        b = Find(b);

        if (a == b)
        {
            cout << i + 1;
            return 0;
        }

        Union(a, b);
    }

    cout << 0;
}

---