백준 20040 사이클 게임

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

문제는 두 플레이어가 번갈아 선분을 긋고, 사이클이 생긴다면 몇 번째에 생겼는지 출력하고 생기지 않았다면 0을 출력하면 되는 문제이다.

입력 조건에서
점의 개수는 3~500,000개이고 차례는 3~1,000,000개이므로 O(nlogn)까지의 알고리즘으로 풀이해야 한다고 느꼈다.

6 5
0 1
1 2
2 3
5 4
0 4

두 예시로 문제를 이해해 보았다.
총 6개의 점(0~5까지)이 있으며, 5개의 선분을 번갈아 가며 그린다.

위 예시에선 사이클이 발생하지 않았으므로 0을 출력하였다.

6 5
0 1
1 2
1 3
0 3
4 5

사이클이 발생하는 예시이다.

0-1-3 세 점에 대해 사이클이 발생하였고, 네 번째 (0 3) 입력이 들어왔을 때 발생하였으므로 4를 출력한다.

위 문제를 풀기 위해 Union-Find 알고리즘을 이용하였다.
두 점을 잇는다는 것을 두 점을 한 집합에 넣는 것으로 판단하고 입력받은 두 점이 같은 집합에 속해있는 경우, 사이클이 발생하는 것으로 판단할 수 있다.

두 번째 케이스로 예시를 들어 보겠다.

6 5
0 1
1 2
1 3
0 3
4 5

먼저 각 점에 대한 집합을 생성한다

0	1	2	3	4	5
0	1	2	3	4	5

첫 번째 행은 점을 뜻하고, 두 번째 행은 해당 점이 어느 집합에 속하는지(다른 어떤 점과 연결 되었는지)를 의미한다.

먼저 (0 1) 입력을 받는다.
0과 1은 서로 다른집합에 속해있으므로 사이클이 생기지 않는다.
따라서 종료시키지 않고 0과 1을 0번 집합에 속한 것으로 묶는다.

0	1	2	3	4	5
0	0	2	3	4	5

다음으로 (1 2) 입력을 받는다.
1은 0번 집합, 2는 2하나의 집합에 속해 있으므로 서로 다른 집합에 속해 사이클이 생기지 않아 이전 입력과 동일하게 처리한다.

0	1	2	3	4	5
0	0	0	3	4	5

현재까지, 0 - 1 - 2를 잇는 선분이 존재한다고 생각할 수 있다.

다음으로 (1 3) 입력을 받는다.
이 케이스 또한 (1 2) 케이스와 유사하므로 동일하게 처리한다.

0	1	2	3	4	5
0	0	0	0	4	5

다음으로 (0 3) 입력을 받는다.
여기에선 0과 3 모두 0번 집합에 속해 있어 0과 3을 연결하는 순간 사이클이 발생하므로 해당 입력 위치에서 4를 출력 후 프로그램을 종료한다.

이해를 도울 수 있을지 모르겠지만 기존 집합의 점들(검은색 선)을 연결한 상태에서 집합에 이미 속해 있는 두 점을 연결하는 경우(주황색 선) 위처럼 사이클이 발생할 수밖에 없다.

위 알고리즘을 통해 작성한 코드는 아래와 같다.

import kotlin.system.exitProcess

lateinit var parent: IntArray

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val (n,m) = readLine().split(' ').map{it.toInt()}

    parent = IntArray(n){it}

    for(i in 1..m){
        val (p1, p2) = readLine().split(' ').map { it.toInt() }
        if(find(p1) == find(p2)){
            print(i)
            exitProcess(0)
        }
        union(p1, p2)
    }
    print(0)
}

fun find(x: Int): Int{
    if(x == parent[x])
        return x
    else{
        val p = find(parent[x])
        parent[x] = p
        return parent[x]
    }
}

fun union(x: Int, y: Int){
    val rootX = find(x)
    val rootY = find(y)

    parent[rootY] = rootX
}

이전에 작성하였던 union-find 알고리즘을 그대로 사용하였다.
1부터 m까지의 for문을 통해 input을 받아오고, 받아온 두 점이 같은 집합에 속한 경우 사이클이 발생한 것으로 간주해 정답 출력 후 종료하도록 하였다.