집합의 표현
-
백준 1717 집합의 표현Algorithm/BOJ 2021. 1. 12. 12:44
출처: https://www.acmicpc.net/problem/1717 분류: 자료구조 접근방식 몰랐는데 disjoint-set(서로소 집합) 문제라고 하네요. 집합이 합쳐지는 걸 어떤 집합에 속하게 된다는 개념으로 접근하면 쉽게 해결할 수 있는 문제였습니다. 배열에는 부모를 저장하고 있고 재귀적으로 최상위 부모를 찾아서 비교하고, 합칠 때도 역시 최상위 부모로 합쳐주면 됩니다 :) 처음엔 문제 그대로 집합을 합쳐주고 원소들을 합쳐진 집합으로 다 바꿔주는 식으로.... 1차원적으로 풀었는데 당연히 시간초과였습니다 흡 * a와 b를 확인하기 전에 같은 경우를 걸러주면 시간을 많이 줄일 수 있습니다 :) 해결방법 import Foundation let input = readLine()!.split(sepa..