devbelly

문제 www.acmicpc.net/problem/12012 알고리즘 Union Find, 오프라인 쿼리 풀이 헛간을 하나씩 닫아나갈 때 마다, 열린 헛간들의 연결성을 확인하는 문제입니다. 헛간을 닫을 때, 인접한 경로 또한 사라집니다. 우리가 아는 자료구조중 유니온 파인드는 조건에 따라 같은 노드들을 하나로 합치는 연산을 수행할 뿐, 합쳐진 노드들을 분리해내지는 않습니다. 연결성을 끊는 것은 쿼리를 거꾸로 보면 연결하는 것과 연관이 있습니다. 즉 쿼리를 순서대로 보지 않고 거꾸로 보며 유니온 파인드로 문제를 해결해 봅시다. 처음에 모든 헛간이 문을 닫은 상태에서 쿼리의 마지막부터 헛간을 다시 열어 나갑니다. 열려있는 헛간들의 연결성을 확인하는 것은 쿼리에 해당하는 헛간의 집합크기를 보면 됩니다. 마지막 ..

문제 www.acmicpc.net/problem/2487 알고리즘 union find 풀이 섞기 수열이 주어질 때, 원래의 카드 순서로 돌아오기 위한 궤적을 구하는 문제입니다. 카드들이 턴마다 어디로 움직이는지 파악해야합니다. 카드들이 섞기 수열에 따라 움직이며 각 카드마다 제자리로 돌아와야합니다. 같은 사이클을 사용하는 카드들의 크기들을 파악한 후 사이클의 최소 공배수를 구하면 궤적이 나오게 됩니다. 아래 유니온 파인드에서 $p$는 자신의 부모를 나타내며, 만약 $p$값이 음수라면 그 인덱스가 부모임을 나타내며 절댓값은 해당 사이클의 크기를 나타내도록 구현했습니다. 코드 #include #include #define rep(i, n) for (int i = 0; i < n; ++i) #define RE..

문제 www.acmicpc.net/problem/12877 알고리즘 union find 풀이 N개의 동물들과 각 관계를 설명하는 K개의 정보가 주어질 때, 모순이 되는 정보들의 갯수를 세는 문제입니다. 문제가 되는 것은 2번 타입의 정보입니다. 동물들마다 3개의 노드를 갖도록 합시다 . 각각은 $i$번째 동물의 타입을 가리키게 됩니다. 구체적으로 $i$번째 동물이 A종류일때는 배열 $i$번이 정보를 갖고 있고 B, C 종류일때는 각각 $i+N$, $i+2*N$ 배열이 정보를 담고 있습니다. 이제 $union$함수를 통해 묶인 그룹은 해당 정보가 동시에 발생한다는 의미를 담는다고 합시다. 이렇게 되면 2번 정보또한 처리가 가능해집니다. 2 X Y가 입력으로 들어왔다면 아래 세 정보를 유니온 해주면 됩니다...

문제 www.acmicpc.net/problem/18267 알고리즘 union find 풀이 트리에서 각 노드마다 소의 종류가 정해져 있을 때, 주어진 쿼리에서 그 사이 경로에 해당 소가 있는지 찾는 문제입니다. 트리에서 인접한 노드가 서로 같은 종류의 소라면 유니온 파인드를 통해 묶어줍시다. 이후 쿼리에서 두 노드의 부모노드가 다르다면 경로상에 두 종류의 소가 있음을 알 수 있습니다. 만약 부모노드가 같다면 그 부모노드의 소가 어떤 종류인지 찾아 비교해주면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i N >> M; memset(p, -1, sizeof(p)); rep(..

문제 www.acmicpc.net/problem/18321 알고리즘 Union find 풀이 $N$개의 지역과 $N$마리의 소가 있습니다. 초기 배치 상태가 주어질 때, $i$번 지역에는 $i$번 소가 있도록 해야 합니다. 소들이 움직이기 위해 wormhole이 주어질 때, 사용하는 wormhole 넓이의 최솟값이 최대가 하도록 요구하는 문제입니다. 최소의 최대화, 최대의 최소화는 익숙한 이분탐색 주제입니다. 이분 탐색 + DFS로도 풀 수 있으나 좀 더 빠른 Union find로 풀이법을 소개해드리겠습니다. 초기에는 모든 지역이 이어져 있지 않다고 가정합시다. 그리디하게 넓이가 큰 간선부터 양 지역을 연결하는 것은 최선의 전략입니다. 정답이 $k$인데 $k+x$넓이의 간선(x는 양수)을 사용하는 것은 ..

문제 www.acmicpc.net/problem/14932 알고리즘 Union-find 풀이 버튼을 순차적으로 나갈 때, 금고를 풀 수 있는지 묻는 문제입니다. 하나의 노드에서 다른 노드로 간다. 라는 점에서 다양한 풀이들을 떠올릴 수 있습니다. 저는 처음에 SCC로 접근하여 컴포넌트의 수를 카운트하여 답을 계산하였습니다. 다른 풀이로는 하나의 노드를 자식으로 다른 노드를 부모로 설정하여 유니온 파인드로 접근하는 것입니다. 각 버튼의 고유값을 매기기 위해 순차적으로 번호를 매겼습니다. (r,c)에 해당하는 번호는 $r*N+j$ 이 됩니다. 입력을 받아 현재 자신이 어디의 버튼을 가리키고 있는지 찾습니다. 그리고 부모-자식관계로 묶어줍니다. 그리고 부모-자식관계가 성립하지 못한 버튼이 있다면 카운트를 해줍..