문제 0에서 n까지 숫자 한개로 이루어진 n+1개의 집합이 있다. 합집합 연산(0)과 두 원소가 같은 집합에 포함되는지 여부를 확인하는 연산(1)을 수행할 때, 같은 집합에 포함되면 yes, 아니면 no를 출력하는 문제이다. 연산은 연산종류(0,1), a원소, b원소 순서대로 입력된다. 풀이 이 문제는 각 원소가 포함된 집합의 대표 번호(부모 노드)를 저장함으로써 합집합 연산에서는 두 원소의 부모 노드를 더 작은 번호로 일치시켜주고 (union) 두 원소의 집합이 같은지 확인하는 연산에서는 부모 노드가 동일한지 확인하면 되기 때문에 (find) 분리집합 알고리즘으로 해결할 수 있다. 먼저 부모 노드들을 담을 parent(p) 리스트를 생성한다. 초기 부모 노드는 각 집합에 담겨있는 숫자의 번호로 초기화한..
[백준 BOJ / Python] 17352번 여러분의 다리가 되어 드리겠습니다!
문제 N개의 섬이 존재하고 이들이 n-1개의 다리로 어떤 두 섬이든 이동할 수 있도록 연결되어 있다. 이때 다리 하나가 파괴되었고 새로운 다리를 연결해야할 때, 어떤 두 섬 사이에 다리를 연결하면 어떤 두 섬이든 이동할 수 있게 되는지 알아내는 문제이다. 풀이 이 문제에서 기존에 어떤 두 섬이든 이동할 수 있었다는 것은 모든 섬들이 하나의 집합을 이루고 있다는 뜻이다. 즉 모두 같은 부모 노드를 갖고 있다는 의미이다. 여기서 다리 하나가 없어졌다는 것은 1개의 집합이 끊어져 2개의 집합이 되었다는 것이다. 따라서 두 개의 집합의 섬(노드) 하나씩을 연결해주면 다시 1개의 집합으로 만들 수 있다. 즉, 두 집합의 부모 노드 끼리 연결해주면 되는 것이다. Union-Find 알고리즘을 사용해 두 개의 분리된..
[알고리즘 / Python] 분리집합 (Disjoint Set / 서로소 집합)
1. 분리집합 (Disjoint Set) 분리집합은 서로 겹치는 원소가 없는 상호 배타적인 집합들을 의미하며 서로소 집합이라고도 불린다. 전체 집합에 대하여 겹치지 않는 두 개 이상의 부분 집합이라 할 수 있다. 즉, 분리집합 알고리즘은 각 원소가 속하는 부분 집합을 찾아 분리를 하는 것이다. 예를 들어, 전체 집합 U에 대하여 짝수 집합 A와 홀수 집합 B는 서로 겹치는 원소가 없는 부분 집합들로 분리집합이라 할 수 있다. 2. Union-Find 알고리즘 시간복잡도: 평균적으로 O(logN)이며, 최악의 경우에는 O(n)이다. 트리구조를 사용한다. 하지만 이때, 자식노드가 부모노드 가리킨다는 것에 차이가 있다. 두 개 노드가 있을 때, 서로 같은 집합에 있는지 아닌지 판별하는 알고리즘이다. Find ..