분리집합2 백준 15352 자바 - 욱제와 그의 팬들 (BOJ 15352 JAVA) 문제 : boj15352 1. 우선 '행동 2'만 존재할 경우 어떻게 풀 수 있을지 확인해보자. 입력으로 주어진 N개의 A값들에 대해 좌우로 인접한 항목이 같은 팬클럽 번호라면 그룹을 지어보자. 이 때, union-find를 사용하고 부모가 되는 노드에 차수를 입력해둔다고 한다면 '행동 2'에 대해 O(1)로 부모의 차수를 출력하는 것 만으로 결과를 낼 수 있다. 예를들어 parents[a]에 대해 parents[a] >= 0일 경우 부모의 번호, parents[a] < 0일 경우 부모 중 하나이며, 그 부모에 그룹지어져 있는 노드의 개수라고 하면 예제 입력 1은 다음과 같이 나타낼 수 있다. union-find의 사용방법은 다양한 편이므로, 어쨌든 해당 그룹에 포함된 개수를 한방에 알 수만 있도록 짜면.. 2022. 2. 4. 백준 9001 자바 - Rectangle Coloring (BOJ 9001 JAVA) 문제 : boj9001 1. 우선 그룹의 개수는 어떻게 구할 수 있을까? 그룹 구하는데 특화된 union-find (분리 집합) 알고리즘을 사용하면 쉽게 그룹이 총 몇개인지 알 수 있다. 2. 그럼 입력받은 직사각형들에 대해 모든 경우를 다 보면서 O(N*N) 서로 직사각형이 겹치는지 여부만 알 수 있다면 union-find로 그룹으로 만들어주고, 최종적으로 그룹의 개수를 출력해주면 된다. 직사각형 겹치는걸 확인하는데 가장 쉬운 방법은 배열에 직접 직사각형에 포함된 면적을 기입하면서 겹치는지 확인하는 것인데, 문제는 이 경우 최대 O(N*10000*10000) 이 걸리므로 불가하다. N이 최대 200인것에 착안해 좌표 압축을 통해 해봐도 된다. 그럼 최대 O(N^3)이면 구해볼 수 있다. 내 경우엔 그냥.. 2021. 12. 22. 이전 1 다음
