[백준] 단계별로 풀어보기(단계:30, 유니온 파인드,JAVA)20040번, 사이클 게임

문제 링크

20040번: 사이클 게임

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

유니온 파인드

 상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위해 만들어진 자료구조

Union : 집합끼리 합치는 연산

Find : 집합의 원소가 어디에 속해있는지 확인하는 연산

Union Find - 나무위키

이 문제에 핵심은

1. 사이클 게임의 입력을 받아서 사이클이 형성될 때 바로 횟수를 출력한다.

2. C는 모든 선분이 아닌 선분의 부분 집합입니다.

3. C집합의 선분을 모두 돌아 출발점으로 돌아오면 사이클이 형성된다고 할 수 있다.

 

새로운 선분을 입력받았을 때 두 지점의 루트 노드의 값이 같다면 사이클이 형성된다고 볼 수 있습니다.

 

같은 루트 노드의 값이면 두 지점은 서로 연결되어 있어서 루트 노드 기준으로 연결된 선분들 사이에 사이클이 형성된다고 볼 수 있다.

  

예제입력1에서 유니온파인드가 어떻게 진행되는지 보여드리겠습니다.

 

빨간색 : 해당 원소의 루트 노드

 

※저는 합집합을 진행할 때 집합의 루트 노드가 더 작은 곳을 루트 노드로 하였습니다.

 

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

 

입력값 : 0 1

해석 : 점 0과 점 1을 이은 선분

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

점 0과 점 1의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

 

입력값 : 1 2

해석 : 점 1과 점 2을 이은 선분

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

점 1과 점 2의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

 

입력값 : 1 3

해석 : 점 1과 점 3을 이은 선분

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

점 1과 점 3의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

 

입력값 : 5 4

해석 : 점 5과 점 4을 이은 선분

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

점 5과 점 4의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

 

입력값 : 0 4

해석 : 점 0과 점 4을 이은 선분

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

점 0과 점 4의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

 

더 이상 입력이 없어서 사이클이 만들어지지 않으므로 결과 0을 출력합니다.

 

 

예제입력2에서 유니온파인드가 어떻게 진행되는지 보여드리겠습니다.

 

빨간색 : 해당 원소의 루트 노드

 

※저는 합집합을 진행할 때 집합의 루트 노드가 더 작은 곳을 루트 노드로 하였습니다.

 

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

 

입력값 : 0 1

해석 : 점 0과 점 1을 이은 선분

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

점 0과 점 1의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

 

입력값 : 1 2

해석 : 점 1과 점 2을 이은 선분

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

점 1과 점 2의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

 

입력값 : 1 3

해석 : 점 1과 점 3을 이은 선분

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

점 1과 점 3의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

 

입력값 : 0 3

해석 : 점 0과 점 3을 이은 선분

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

점 0과 점 3은 루트 노드가 같으므로 사이클이 만들어진다.

사이클(3-0-1-3)이 만들어졌으므로 결과 4가 출력됩니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 사용하여 선분에 대한 정보를 저장합니다.
• 선분에 대한 정보로 union함수로 동일한지 비교 및 루트 노드를 변경하였습니다.
• BufferedWriter에 루트 노드가 동일했을 때 횟수를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• find는 재귀탐색을 이용하여 루트 노드의 값을 찾는 함수입니다.
• union은 루트 노드를 비교 및 루트 노드 변경하는 함수입니다.

결과 코드

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

public class Main {
	static int n,m,result=0;
	static int[] root;	//루트 노드 저장하는 배열
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		root = new int[n];
        	//루트 노드 초기화
		for(int i=0;i<n;i++) 
			root[i] = i;
		//선분의 입력값 저장
		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(union(a,b)) {
				result = i+1;	//루트 노드 동일하면 횟수 저장
				break;
			}
		}
		bw.write(result + "\n");	//횟수 BufferedWriter 저장
		bw.flush();	//결과 출력
		bw.close();
		br.close();
	}
    	//루트 노드 찾는 함수
	static int find(int n) {
		if(n==root[n])
			return n;
		return root[n] = find(root[n]);
	}
    	//루트 노드 비교 및 변경하는 함수
	static boolean union(int a, int b) {
		int x = find(a);
		int y = find(b);
		if(x==y) {
			return true;
		}
		if(x!=y) {
			if(x<y)
				root[y] = x;
			else
				root[x] = y;
		}
		return false;
	}
}