[알고리즘 문제 풀기] 사이클 게임(20040)

1. 문제 풀이 아이디어

• Union-Find로 각 간선을 순차 처리하며 두 노드가 이미 같은 집합에 속하면 사이클이 발생함을 감지하고 해당 단계를 반환하여 문제를 해결할 수 있다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    string[] split = sr.ReadLine().Split();

    int n = int.Parse(split[0]);
    int m = int.Parse(split[1]);

    int[] parent = new int[n];
    for (int i = 0; i < n; i++)
    {
        parent[i] = i;
    }
    int result = 0;
    for (int i = 0; i < m; i++)
    {
        split = sr.ReadLine().Split();
        int a = int.Parse(split[0]);
        int b = int.Parse(split[1]);
        if (Union(a, b))
        {
            result = i + 1;
            break;
        }
    }
    sw.WriteLine(result);
    bool Union(int x, int y)
    {
        int rX = Find(x);
        int rY = Find(y);

        if (parent[rX] == parent[rY])
            return true;
        if (rX > rY) parent[rX] = rY;
        else parent[rY] = rX;
        return false;
    }
    int Find(int x)
    {
        if (parent[x] == x)
            return x;
        return Find(parent[x]);
    }
}

3. 정리

• parent 배열을 인덱스로 초기화하여 각 노드를 자기 자신을 가리키도록 설정한다.

• 입력받은 두 노드의 루트를 Find로 탐색한다.

• 찾은 두 루트가 같으면 사이클이 발생한 것이므로 현재 단계(i+1)를 결과로 저장하고 반복을 종료한다.

• 루트가 다르면 더 작은 값을 부모로 설정하여 Union을 수행한다.

• Find 함수는 재귀적으로 부모를 따라가며 최종 루트를 반환한다.