백준 union find 알고리즘, 17171 집합의표현 swift 풀이

 

 

 

---

백준 17171번, 집합의표현 문제 알아보기

 

 

1717번, 집합의 표현 문제는 disjoint-set, 서로소 집합 관련 문제입니다. 서로소 집합 개념은 MST문제을 풀때 자주 사용하는 크루스컬 알고리즘에서도 활용되는 유용한 개념입니다. 

 

본 문제 난이도는 solved.ac기준, 골드4로 일반 코딩테스트 기준, 중후반대에 나올 수 있는 문제입니다. 

 

 

 

 

 

 

시간제한은 2초, 메모리 제한은 128MB입니다. 

 

 

 

 

 

 

초기에 {0}, {1}, {2}, .... {N}의 N+1개 집합이 있다고 할때, 이에 대한 합집합 연산, 두 원소가 같은 집합에 포함되어 있는지 확인하는 연산을 출력하는 문제입니다. 이렇게까지만 문제를 보면 단순한 문제로 보일 수도 있지만, N의 입력범위가 최대 백만이란 점에서, disjoined-set 기반의 union-find 개념을 활용하지 않으면 제한시간내에 풀기 어렵습니다.

 

union-find 알고리즘은 서로소 집합 개념에서 합집합 연산이 된 노드의 부모노드를 하나로 통합해감으로서, 각 노드가 합쳐진 상태인지 여부를 보다 효율적으로 찾을 수 있는 알고리즘입니다.

 

 

 

 

 

 

노드의갯수(N), 연산의 갯수(M)을 입력 받고, 이후에 연산 명령이 주어집니다.

 

"0 1 3"은 노드 1, 3을 합치라는 의미입니다. "1 4 2"는 노드 4, 2가 같은 집합에 있는지에 따라 "YES"나 "NO"를 출력해주어야 합니다. 

 

 

 

 

 

union-find 문제를 풀기 전에 union-find를 하면 어떤 식으로 각 노드의 부모노드 값이 바뀌어가는지를 위의 코드로 보고 넘어가겠습니다.

- 0 1 2 1 4 5 6 7 : 합집합 연산으로 1번째, 3번째 노드의 부모노드가 1로 같아졌습니다.

- 0 1 2 1 4 5 6 6 : 6, 7번째 노드의 부모노드가 6으로 같아졌습니다.

- 0 1 2 1 4 5 1 6 : 6번째 노드가 1, 3번째 노드의 부모노드와 같아졌습니다.

.

.

.

 

위의 union find 연산과정과 같이 합집합 연산이 되는 두 노드는 하나의 부모 노드로 통합되며, 이를 통해 특정 노드 두개가 동일한 집합 내에 속해있는 지를 확인할 수 있게 됩니다. 

 

이어서 swift언어로 서로소 집합의 union-find 연산을 하면서 문제를 풀어보겠습니다.

 

 

 

---

백준 17171번, 집합의표현 swift 문제풀이

 

 

3행) answer는 정답결과를 쌓아둘 예정인 배열입니다.

4 ~ 17행) 보다 빠른 성능으로 문제를 풀기위해 구현한 입력 최적화 구현 코드입니다. 한줄 입력을 받았을때 입력받은 문자열 String을 [Int] 타입의 배열로 반환해주는 클로져 함수 ip입니다. 

 

 

 

 

 

 

20행) 먼저, N, K(M)을 입력 받습니다.

21행) 각 노드의 부모노드 번호를 기록할 Parent배열입니다. 각각의 노드의 부모노드는 초기에 본인 노드를 가리키고, 이후 union-find 연산으로 부모노드가 하나하나 통합되어갑니다.

 

 

 

 

 

 

특정 노드의 부모노드를 반환하는 재귀함수입니다. getParent는 Parent[node] == node를 통해 현재 노드가 부모노드인지 확인하고, 아니라면 재귀를 통해 현재 노드의 진짜 부모노드가 무엇인지를 찾아나갑니다. 

 

26행) Parent[node] = getParent(Parent[node]) 가 바로 각 노드의 부모노드를 갱신해주는 코드입니다. 이후 부모노드를 구할때 더 빠르게 현 노드의 부모노드를 찾을 수 있게 됩니다. 

 

 

 

 

 

 

mergeParent는 앞서 보았던 디버깅 출력 결과처럼, 합집합 연산이 된 두 노드의 부모노드를 동일하게 만드는 과정입니다. A, B노드의 부모노드를 구하고, 두 부모노드 중 작은 부모노드로 두 노드의 부모노드를 통일합니다. 

 

 

 

 

 

 

이제 M(K)번의 연산 수행을 통해서 합집합 연산, 두 노드가 동일 부모노드인지를 출력하는 연산을 수행합니다. 

 

38행) 연산을 할 명령을 arr2로 받고 있습니다.

40 ~ 43행) T가 0이라면 두개의 부모노드가 다를 경우 mergeParent로 부모노드를 통합합니다.

44 ~ 47행) T가 1이라면, 두 노드의 부모노드가 동일한지를 확인하고 "YES", "NO"를 출력해주면 됩니다.

58행) 마지막으로 출력할 문자열을 모아둔 answer배열의 문자열은 joined를 통해서 하나의 문자열로 합친 후 출력하는 모습입니다. 개행단위 출력이므로 separator: 인자에 "\n"을 넣어서 출력했습니다. 

 

이렇게 disjoint-set의 union find 알고리즘 개념을 통해서 문제를 풀어보았습니다. 그 제출 결과는 아래와 같습니다.