b20040. 사이클게임

 

 

 

🔁 자바로 푸는 사이클 게임 문제 풀이

 

---

 

📌 문제 개요

 

백준 20040 - 사이클 게임 문제는

N개의 정점이 있고, M개의 간선을 순차적으로 연결할 때

사이클이 처음 생기는 시점을 출력하는 문제입니다.

 

• 간선은 차례로 연결되며,
• 간선을 연결할 때 사이클이 생기면 그 **차례(1-indexed)**를 출력
• 끝까지 사이클이 없으면 0을 출력

 

---

 

💡 예제 입력

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

 

예제 출력

4

 

---

 

🧠 알고리즘 접근 방식

 

이 문제는 전형적인 Union-Find(서로소 집합) 알고리즘을 활용해

사이클을 탐지하는 문제입니다.

 

• 간선을 하나씩 연결하며, 두 노드가 이미 같은 집합이면 사이클 발생
• 그렇지 않으면 두 집합을 합침 (union)
• 사이클이 생긴 첫 번째 간선의 번호를 출력

 

---

 

🧾 코드 해설

// 부모 배열 초기화
p = new int[N + 1];
for (int i = 1; i <= N; i++) {
    p[i] = i;
}

// 간선마다 사이클 여부 체크
for (int i = 0; i < M; i++) {
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());

    if (find(a) == find(b)) {
        sb.append(i + 1);
        check = false;
        break;
    } else {
        union(a, b);
    }
}

private static int find(int a) {
    if (a == p[a]) return p[a];
    return p[a] = find(p[a]); // 경로 압축
}

private static void union(int a, int b) {
    int pa = find(a);
    int pb = find(b);

    if (pb < pa) {
        int temp = pa;
        pa = pb;
        pb = temp;
    }
    p[pb] = pa;
}

 

• find(): 부모 노드를 찾아 경로 압축
• union(): 작은 번호를 부모로 삼아 병합 (정렬은 선택)
• 사이클 판별: find(a) == find(b)일 때 사이클 발생

 

---

 

✅ 핵심 포인트

 

• Union-Find로 연결 여부를 추적
• 사이클은 두 정점이 이미 같은 집합에 있을 때 생긴다
• 문제의 핵심은 사이클이 처음 생기는 시점을 찾는 것이다

 

---

 

🎯 결론: Union-Find로 사이클을 잡아내다

 

이 문제는 DFS, BFS 없이 집합만 관리해도 사이클을 감지할 수 있다는 점에서

그래프의 핵심적인 사고인 “연결과 집합”을 연습하기에 좋은 문제입니다.

 

연결 → 같은 집합

사이클 → 이미 연결된 집합에 또 연결하려 할 때