[백준 1717] 집합의 표현(java)-유니온 파인드(Union-Find,합집합)

문제 보러 가기

1717번: 집합의 표현

이 문제는 유니온 파인드라는 알고리즘을 이용하여 합집합을 만들고, 판단하는 문제이다.

자료구조를 코드로 만들어 표현하는 부분을 더 연습해야겠다고 생각했다!

 

 

 

 

 

유니온 파인드(Union-Find) 알고리즘이란?

 

• 그래프 알고리즘 중 하나이다. 분리 집합, 합집합 찾기의 의미를 갖는다.
• parent [] 배열로 각 노드가 어떤 부모 노드 아래에 있는지 그래프로 만든다.

x	1	2	3
parent[x]	1	2	3

 

 -> 초기 parent[] 배열은 노드마다 분리되어 있으므로 자신의 노드 번호를 가진다.

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

 

 

 

• 2가지 연산으로 이루어진다.

  -> 1. find(x) : x가 어떤 집합에 속해있는지 찾는다.

- 가장 상위의 노드 x의 경우 x == parent [x] 관계가 성립한다.

- 따라서 재귀를 통해 집합의 가장 상위 노드를 찾아 return 한다. 

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

 

  -> 2. union(x, y) : x와 y가 포함된 집합을 합친다.

- 집합의 가장 상위 노드로 같은 집합임을 나타내게 되는데, 숫자가 작은 노드를 상위 노드로 선택하여 진행(반대도 o)

- 이미 같은 집합이라면 parent [x]==parent [y] 이므로 갱신이 필요치 않음

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;
    }
}

 

+ 같은 parent[]값을 갖는지 즉, 같은 집합인지 판단

- find()를 재귀로 관계를 타고 들어가게 됨.

static boolean isSameParent(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y)
        return true;
    else
        return false;
 }

 

 

 

 

그래프와 표로 알아보기

1. {1} , {2,3}의 집합인 상태

x	1	2	3
parent[x]	1	2	2

 

2. 두 집합을 연결, -> union(1,3)을 수행

- parent [3]인 2번의 노드의 값이 1로 경신된다.

x	1	2	3
parent[x]	1	1	2

3. 1과 3이 같은 집합인지 확인 -> isSameParent(1,3)

- find() 재귀를 통해 parent [1] == parent [3]인지 확인하게 됨.

- 가장 숫자가 작은 노드 1번을 parent [] 값으로 모두 갖게 되어 하나의 합집합인 것을 알 수 있다.

x	1	2	3
parent[x]	1	1	1

 

 

 

 

 

 

 

문제풀이

-uinon-find를 사용하여 합집합의 관계를 형성한다.

-같은 집합에 속해 있다면 -> find(x) == find(y) => parent [x] == parent [y] YES 아니면 NO를 출력.

 

 

 

public class Ex_1717 {

	static int[] parent;
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		parent = new int[n+1];
		for(int i=0;i<=n;i++) {
			parent[i]=i;
		}
		while(m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int type = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if(type==0)
				union(a,b);
			else
				bw.append(isSameParent(a, b) ? "YES\n" : "NO\n");
			
		}
		bw.flush();
	}
	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;
        else 
            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;
    }

}

 

 

 

무언가 잘못된 것이 있다면 댓글로 달아주세요!