Union-Find

1. 개요 안녕하세요. 오늘 문제의 유형은 Minimum Spanning Tree, MST(최소 신장 트리)입니다.  N개의 별을 선으로 직/간접적으로 연결해야 합니다. 정점을 별, 별을 잇는 선을 간선이라고 한다면 별자리는 트리 구조임을 알 수 있어요! 그런데 선을 연결하는데 비용이 드네요? 이 비용을 최소화하여 연결하고 싶다고 하였으니 가중치 무방향 연결 그래프에서 최소 신장 트리를 구해야 한다는 사실을 알 수 있습니다.  간선의 가중치 정보가 실수형입니다. 부동소수점 연산은 연산을 거듭할수록 오차범위가 커지게 되므로 연산 작업을 최소화해서 푸는 것이 좋습니다. 하지만 이번 문제는 입력부터 실수로 주어져 이를 적용하기 어려운데요. 저는 가중치를 sqrt하지 않은 제곱 형태로 저장해서 풀이했습니다. 의..

1. 문제 풀이 각 칸을 하나의 집합이라는 관점으로 본다면 disjoint-set의 형태로 치환할 수 있습니다. union-find를 union by size로 구현한 다음 flood fill 기법으로 이동할 수 있는 칸들을 서로 union 하여 크기를 구할 수 있습니다. loop를 돌면서 벽인 곳을 찾아 인접한 네 칸을 확인하여 이동할 수 있는 칸이라면 집합의 크기를 더해주어 출력하시면 됩니다. 이때 인접한 칸 중 서로 같은 집합인 경우가 존재하므로 이진트리 set를 이용해 중복을 제거하여 구해주었습니다. 알고리즘 분류를 까보았는데 분리-집합과 이진트리가 빠져있는걸보면 정해가 존재하고 이건 별해인 것 같습니다. 2. 코드#include using namespace std;typedef long long..

1. 문제 풀이gi가 주어졌을 때 1번부터 gi 중 아직 도킹하지 않은 게이트를 찾는 쿼리를 최적화하는 것이 중요한 문제 같습니다. 배열 p의 값을 p[x] = x를 가지게 한 다음 유니온 파인드의 경로 압축을 응용하여 도킹할 게이트를 찾게 하여 최적화하였습니다. p[x] = x인 값을 찾으면 아직 도킹하지 않은 게이트 번호입니다. 도킹을 시도한 다음 p[x]를 1 감소하여 p[x]를 x-1로 갱신해 p[x-1]에서 게이트 번호를 찾게끔 구현하였습니다. 이 때 찾은 번호가 0이면 더 이상 도킹이 불가능하다는 base condition도 추가하였습니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull..

1. 문제 풀이 union-find를 통해 친구 관계를 이어주었다. 여기서 루트 값에 사탕의 개수를 넣어주었고, 각 집합의 인원수는 다른 배열에 저장하여 union을 진행했다. 이를 이용하여 knapsack dp를 사용하여 특정 집합의 인원을 표기해 주었다. knapsack 문제를 정말 오랜만에 풀어서 많이 헤매게 되었다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; ty..

1. 문제 풀이 문제를 처음 읽었을 때, 그래프 자료구조에 간선이 하나씩 추가될 때마다 dfs를 통해 사이클을 탐지하는 naive 한 풀이 방법이 먼저 떠올랐습니다. 문제의 입력을 그래프 자료구조로 보게 되면 정점이 n개이고 간선이 m개인 그래프를 입력받는데 정점이 최대 500'000개이고 간선은 1'000'000개라 이러한 풀이 방법은 시간 내 정답을 구할 수 없다는 생각이 들었습니다. 생각의 발상으로 분리 집합(disjoint-set)을 구현하는 union-find 알고리즘을 사용하면 이 문제를 풀이할 수 있습니다. 두 선분을 잇는다를 두 점을 한 집합으로 union한다고 생각하시면 됩니다. 사이클을 탐지하는 방법은 이 union-find가 진행되는 과정을 그림으로 그려보시면 알 수 있는데 서로 같은..

1. 문제 풀이안녕하세요. 오늘 풀어볼 문제는 "백준 17352번 여러분의 다리가 되어 드리겠습니다!"입니다. 문제의 유형은 "disjoint-set"입니다. distjoint-set은 분리집합이라고 하며 이를 구현한 알고리즘을 union-find라고 합니다. 관련 알고리즘을 모르신다면. 유니온-파인드 알고리즘 링크를 클릭해서 내용을 공부하시고 풀어보시길 바랍니다. 정점이 N개이고 간선이 N-1개인 무방향 연결그래프에서 임의의 간선 하나를 삭제한 무방향 비연결 그래프가 주어졌을 때, 하나의 간선을 다시 이어 연결그래프가 되는 간선 하나를 아무거나 찾아 출력하면 됩니다. 입력으로 주어진 간선이 잇고 있는 두 정점 정보를 union 하게 되면 최종적으론 두 개의 집합이 됩니다. 그 두 집합에서 각각 아무 정..