[백준 20040] 사이클 게임 ( 골드 4)

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

 

유니온 파인드 관련된 문제를 찾아서 진행했다.

두 점을 연결하는 과정을 거치면서 사이클이 완성되면 끝나는 게임이다.

 

두 점을 union하면서 isSameParent 로직으로 확인하면서 cycle이 발생하면 몇 번째 union 에서 발생했는지 출력하면 된다.

* 중요 -> union하면서 parent[] 배열로 부모 점을 계속 변경해주어야 한다. 이때는 둘 중 작은 수로 부모를 변경해야 한다.

union -> 두 점을 연결하고 같은 부모를 바라보게 한다.

find -> 각 점의 부모를 찾는다.

isSameParent -> 부모가 같은지 확인한다.

 

최종 코드

package baekjoon._20040;

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

/* https://www.acmicpc.net/problem/20040 */
public class Main {
	static int[] parent;
	static int n, m;
	static boolean isCycle;
	static int answer;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		parent = new int[n + 1];
		for (int i = 1; i < n + 1; i++) {
			parent[i] = i;
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			if (!isSameParent(x, y)) {
				union(x, y);
				answer++;
			} else {
				isCycle = true;
				answer++;
				break;
			}

		}
		if (isCycle) {
			System.out.println(answer);
		} else {
			System.out.println(0);
		}

	}

	static void union(int x, int y) {
		x = find(x);
		y = find(y);

		if (x != y) {
			if (x < y)
				parent[y] = x;
			else
				parent[x] = y;
		}

	}

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

	}

	static boolean isSameParent(int x, int y) {
		x = find(x);
		y = find(y);

		if (x == y) {
			return true;
		} else {
			return false;
		}
	}
}

 

심화문제로는 친구 네트워크 4195(골드 2)를 추천한다.

아래는 4195번 힌트이다!

해당 문제는 숫자가 아닌 이름으로 주어져서 Map 자료구조를 활용해야하고, union할 때 합집합 연산을 추가로 해줘야 한다.