[백준] 1717번: 집합의 표현
문제
https://www.acmicpc.net/problem/1717풀이
이 문제는 disjoint-set문제로서 union-find로 풀었다.disjoint-set(서로소 집합) : 교집합이 공집합인 집합
Union(a, b) : a가 속한 집합과 b가 속한 집합을 합집합
Find(a) : a가 속한 집합의 번호를 반환
|
i
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
arr[i]
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
입력 n = 7일때, 서로소 집합의 초기값은 위의 표와 같이 되어있다.
Find(1)을 하면 arr[1]==1이므로 1을 return한다.
만약에 같지 않을 경우, 재귀적으로 원소의 부모를 쫓아 올라간다.
Union(1, 3)을 하면 먼저 Find를 각각한다. 그러면 pa=1, pb=3이 된다.
둘은 다른 그룹에 있기 때문에 arr[1]=3으로 그룹 번호를 업데이트 해준다.
|
i
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
arr[i]
|
3
|
2
|
3
|
4
|
5
|
6
|
7
|
이런 식으로 쭉 진행한다.
union-find를 이용하여 kruskal algorithm으로 mst찾는데 쓰인다.
결과
Union연산에서 if(pa != pb) 면 그룹번호를 갱신하도록 조건이 있는데
시간을 단축시키기 위함이다.
이 문제에서는 없어도 맞았다고 한다!
댓글
댓글 쓰기