문제 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) 면 그룹번호를 갱신하도록 조건이 있는데 시간을 단축시키기 위함이다. 이 문제에서는 없어도 맞았다고 한다! 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/1
댓글
댓글 쓰기