[백준/JAVA] 20040_사이클 게임

백준🔗

20040번: 사이클 게임

 

 

문제

 

 

간단 풀이

점들 사이에 사이클이 생겼는지 판단하려면, 선분으로 이어진 점들을 하나의 집합으로 관리하다가 다음에 이으려고 하는 두 점이 같은 집합에 속해 있다면 사이클이 생기는 것으로 판단하면 된다. 

따라서 어제 풀었던 문제와 같이 Union-Find를 적용해 주면 된다.

 

👇어제 풀었던 문제 보러가기 

2023.06.12 - [알고리즘/백준] - [백준/JAVA] 10775_공항

 

 

어제 작성했던 코드의 findSet에도 경로 압축이 적용되어 있었다. (어제는 서로소 집합, 합집합 개념이 너무 오랜만이라 경로 압축의 개념을 잊고 있었다..ㅎㅎ)

원래는 findSet을 실행할 때마다 해당 노드에서 루트 노드까지 찾아가는 과정을 반복적으로 수행해야 하는데, 경로 압축을 적용하면 각각의 노드가 루트 노드를 가르키고 있기 때문에 한 번 만에 루트 노드를 찾아갈 수 있어서 연산의 효율이 높아진다.

오늘도 경로 압축을 적용해서 연산의 효율을 높일 수 있도록 했다.

경로 압축(Path Compression)이란??

Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꾸어 준다.

[의사코드]

Find-Set(x){
	if x != p[x] : 
		p[x] <- Find-Set(p[x])
	return p[x] 
}

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[] points;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 점 개수 (3 ~ 500,000)
		int m = Integer.parseInt(st.nextToken()); // 진행된 차례 수 (3 ~ 1,000,000)

		points = new int[n];

		// 새로운 멤버 i를 포함하는 새로운 집합 생성
		for (int i = 0; i < n; i++) {
			points[i] = i;
		}

		// 게임 진행 상황 입력 받기
		int cnt = 1;
		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 (findSet(A) == findSet(B)) { // 같은 집합에 있는 두 점이면 사이클 발생
				break;
			}
			union(A, B);
			cnt++;
		}
		if (cnt <= m) { // m번째 차례 전에 종료된 경우
			System.out.println(cnt);
		} else { // m번째 차례 전에 종료되지 않은 경우
			System.out.println(0);
		}
	}

	// x를 포함하는 집합의 대표자 반환 (경로 압축 : 모든 노드들이 직접 root를 가리키도록 바꿔줌)
	static int findSet(int x) {
		if (points[x] != x) {
			points[x] = findSet(points[x]);
		}
		return points[x];
	}

	// 합집합 (x 집합에 y 집합 포함시키기)
	static void union(int x, int y) {
		points[findSet(y)] = findSet(x);
	}
}

 

참고 자료