20040 - 사이클 게임

이 문제는 사이클 게임을 할 때, 사이클 게임에서 사이클이 몇 번째 차례에서 완성되었는지 판별해야 하는 문제이다. 여기서 사이클 게임이란 두 플레이어가 번갈아가며 n개의 점에 대해 선분을 긋는 게임으로, 사이클이 완성되면 게임이 종료된다.

이 문제에서 플레이어들이 그은 선분이 사이클을 이루는 순간을 어떻게 인식할 수 있을까? 먼저 사이클이 어떤 특성을 갖는지부터 생각해보자. 어떤 점을 선분으로 연결했을 때, 그 선분들이 사이클을 이룬다면, 어떤 점을 시작점으로 잡았을 때 선분을 타고 계속 이동하다 보면 최종적으로 시작점에 다시 도달하게 된다. 즉 사이클을 이루는 임의의 점은 앞으로 이동하든 뒤로 이동하든 시작점에 도달한다.

위 탐구 내용을 바탕으로 사이클이 생성되는 조건을 잘 생각해보자. 어떤 점이 이미 임의의 시작점 s로 이동할 수 있고, 동시에 새 선분을 통해 다시 s와 연결될 때 사이클이 생긴다는 것을 알 수 있다. 따라서 기존에 연결된 점들의 시작점이 어디인지 관리해두고 선분에 의해 새로 연결되는 두 점의 시작점이 서로 같다면 사이클이 생성된 것으로 간주할 수 있다.

직관을 일반화하면 다음과 같다.

무방향 그래프에서 간선 (a, b)를 추가할 때 a와 b가 이미 같은 연결요소(같은 집합)에 있으면, 그 간선을 추가하는 순간 사이클이 생긴다.

위 논리를 간편하기 구현하기 위해 필요한 것이 disjoint set(union-find) 이다. 선분이 새로 연결될 때마다 union 연산을 통해 같은 집합에 담아두고, 두 점의 시작점이 같은 점인지 검사하기 위해 find 연산을 사용할 수 있을 것이다.

🔗 문제 링크

코드

먼저 union-find 구현 코드를 살펴보자. parent 배열의 경우 각 원소의 루트를 저장해두기 위한 변수이고, rank의 경우 각 원소의 트리에 대한 병합 기준을 저장해두기 위한 변수이다. init 함수의 경우 union-find가 다룰 원소의 개수 n을 인자로 받아 배열을 할당하고, 각 원소의 parent를 자기 자신의 번호로 설정해 둔다. union 함수의 경우 서로 다른 두 집합 a, b의 합집합을 구하는 함수이고, find는 원소 x가 속한 집합, 혹은 원소 x가 속한 집합의 대표값을 구하는 함수로 해석할 수 있다. 이 구현의 경우 Path compression 및 Union by rank를 적용하여 시간복잡도를 줄였다.

static int[] parent;
static int[] rank;

static void init(int n) {
    parent = new int[n];
    rank = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
}

static void union(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);

    if (rank[rootA] < rank[rootB]) {
        int tmp = rootA;
        rootA = rootB;
        rootB = tmp;
    }

    rank[rootA] += rank[rootA] == rank[rootB] ? 1 : 0;
    parent[rootB] = rootA;
}

static int find(int x) {
    if (x == parent[x]) return x;
    parent[x] = find(parent[x]);
    return parent[x];
}

메인 함수에서 점의 개수 n과 그은 선분의 개수 m을 입력받는다. 각 점들에 대해 시작점이 어딘지 다룰 것이므로 n으로 disjoint set 크기를 설정해 초기화한다.

public static void main(String[] args) throws IOException {
    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    init(n);

다음으로 선분의 연결 정보를 입력받아 사이클이 완성되었는지 확인한다. 선분이 잇는 점 a, b를 입력받은 뒤, a의 시작점과 b의 시작점이 같은지 검사한다. 만약 같을 경우 사이클이 완성된 것이므로 완성된 순서를 출력해준 뒤 프로그램을 종료한다. 만약 시작점이 같지 않을 경우 union 연산을 통해 같은 시작점을 가지도록 처리해준다. 만약 m개의 선분에 대해 모두 확인하여도 사이클이 완성되지 않았다면, 아직 종료되지 않은 것이므로 0을 출력한다.

    for (int i = 0; i < m; i++) {
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        if (find(a) == find(b)) {
            System.out.println(i+1);
            return;
        }

        union(a, b);
    }
    System.out.println(0);
}

전체 코드

import java.util.*;
import java.io.*;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int[] parent;
    static int[] rank;

    static void init(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if (rank[rootA] < rank[rootB]) {
            int tmp = rootA;
            rootA = rootB;
            rootB = tmp;
        }

        rank[rootA] += rank[rootA] == rank[rootB] ? 1 : 0;
        parent[rootB] = rootA;
    }

    static int find(int x) {
        if (x == parent[x]) return x;
        parent[x] = find(parent[x]);
        return parent[x];
    }

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        init(n);
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if (find(a) == find(b)) {
                System.out.println(i+1);
                return;
            }

            union(a, b);
        }
        System.out.println(0);
    }
}

시간복잡도

union 혹은 find 연산을 한 번 수행할 때의 시간복잡도는 $O(\alpha(n))$으로 알려져 있으며, 이 문제에서는 연산을 최대 $m$번 수행하기 때문에 이 프로그램의 시간복잡도는 $O(m \cdot \alpha(n))$ 이 된다.