# Union Find

timosean

문제 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한 사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입니다. 임의의 i에 대해, costsi 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다. 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어

steady_aa

문제링크 https://www.acmicpc.net/problem/1717 구현방법 기본적으로 각 배열이 존재함. n은 100만개 m은 10만개 2중 돌면 터짐. -> O(N) 안쪽으로 생각해야함. List 형식이 나은가 a와 b 가 같은 경우 합집합 둘이 같은 원소일 때 굳이 합칠 필요가 있는가? 없다고 생각하기 때문에 넘어감. a와 b 가같은경우 ?? 2중 ArrayList 그래프 만들듯이 진행하고 -> 여기서 for문이 엄청 돌아가게 된다는 것을 알게되어 포기 UnionFind 기초문제 둘이 묶으면 좋겠다는 생각이 들었지만 처음에 UnionFind 알고리즘은 생각이 나지 않았음. 부모가 같으면 같은 집합에 포함된다는 것을 이용해서 빠르게 구할 수 있음. 알고리즘 Union-Find CODE

papamoon0113

https://youtu.be/aOhhNFTIeFI 영상 내용 정리 0. 기본 용어 서로소 : 어떤 두 집합이 서로 공통 원소가 없으면, 두 집합을 서로소 관계라고 함 서로소 집합 자료구조 : 서로소인 집합들로 나누어진 데이터를 처리하기 위해 쓰이는 자료구조 Disjoint Set Union, Union-Find 등 이름이 여러가지임 보통 노드를 key로 가지는 테이블로 구현됨 1. DSU의 기본 연산 Union(v1, v2) : v1과 v2가 포함되어 있는 집합들을 하나의 집합으로 합치는 연산 예 : {1, 2, 3} {4, 5, 6} → Union(1, 4) → {1, 2, 3, 4, 5, 6} Find(v1) : v1이 속한 집합이 어떤 집합인지 알려주는 연산 ( 그 기준은 보통 root 노드 ) 예 : 1

dbwogml15

[1976-여행 가자] 문제 N 도시의 수 M 여행 경로의 수 인접행렬 입력 여행 경로 입력 여행 경로가 유효한가?를 묻는 문제다. 즉, 인접 행렬에 노드간 간선으로 이루어져 있는지 정보를 주고 여행 경로(노드 이동 경로)가 가능한지 묻는 문제다. 풀이 이 문제는 Union Find로 풀이할 수 있다. 간선으로 이어진 도시들(노드들)을 합집합으로 같은 루트 노드를 바라보게하고 여행 경로를 순회하면서 같은 루트를 바라보고 있는지 검사하면 문제가 해결된다. 코드 입력값과 초기 선언문 때문에 코드가 길지

dbwogml15

[[20040-사이클 게임]] (https://www.acmicpc.net/problem/20040) 문제 입력으로 점 N개와 (0 ... N - 1) 임의의 점을 잇는 선분 M개가 주어진다. 몇번째 선분에서 사이클이 생기는지 출력하는 문제, 사이클이 생성되지 않으면 0을 반환한다. 풀이 간단한 Union Find 문제다. 선분을 잇는다 = 합집합 연산 즉, 같은 루트 노드를 바라보도록 만들어 주면서 이미 루트노드가 같다면 같은 집합에 있는 점을 잇는다면 사이클이 형성될 것이다. 위의

dbwogml15

[[1043-거짓말]] (https://www.acmicpc.net/problem/1655) 문제 N 사람의 수 ( 1 <= N <= 50 ) M 파티의 수 ( 1 <= N <= 50 ) 진실을 아는 사람이 주어졌을때 거짓말을 할 수 있는 파티의 수를 구하는 문제 파티에 참석하는 인원이 주어진다. 풀이 진실을 아는 사람들이 존재하는 파티, 그 파티에 참석하는 인원들을 모두 합집합 연산하여 해결할 수 있다. Union Find 처리 순서는 아래와 같다. 같은 파티에 참석하는 인원들이 같은 부모를 바라보도록 처리해준다 (Union) 진실을 아는 사람들의 부모 노드를 파악하여 해당 부모 노드를 갖는 노드들을 모두 진실을 아는 사람들로 처리해준다.

dbwogml15

[[1717-집합의 표현]] (https://www.acmicpc.net/problem/1717) 문제 입력받은 n에 대해 n + 1개의 서로소 집합이 존재한다. 0 ~ n 원소는 자기 자신 입력받은 m개의 커맨드가 입력된다. [연산] [타겟 숫자1] [타겟 숫자 2] 연산이 0일 경우 두 타겟 숫자가 속한 집합을 합집합 연산 연산이 1일 경우 두 타겟 숫자가 같은 집합인지 검사 후 YES or NO 출력 풀이 Union Find를 사용하는 기본적인 문제다. 위 그림과 같

sseq007

문제 링크 https://www.acmicpc.net/problem/20040 > 문제 풀이 이 문제는 유니온 파인드를 이용하여 풀었다. 사이클이 존재할려면 각 부모가 같으면 존재한다. 존재하지 않는다면 각 노드를 union 시킨다. >부모찾기 find 함수 >union 함수 >전체 코드

i_am_gr00t

문제 10775번: 공항 풀이 큰 수의 비행기는 작거나 같은 수의 게이트에 도킹이 가능하다. 큰수의 비행기가 작은 수의 게이트에 먼저 도킹을 하게 되면 나중에 작은 수의 비행기가 그 게이트에 도킹을 못하게 되므로 비행기는 가능한 가장 큰 수의 게이트에 도킹해야 한다. N 비행기가 N 게이트에 도킹을 했다면, 다음 N 비행기는 N-1 게이트에 도킹을 해야한다. 이렇게 이미 도킹되어 1 작은 게이트에 도킹해야 한다면 N과 N-1을 같은 집합으로 묶어 N이든, N-1이든 모두 N-1로 취급하여 처리하면 된다. 이때 Union-Find 알고리즘을 사용한다. 도킹할 게이트를 찾기 위해 find(N) 함수를 사용한다. 비행

hsh111366

https://www.acmicpc.net/problem/4195 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다. 출력 친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을

lyouxsun

Union-Find 알고리즘 이용하기!!! 처음 생각한 풀이 (오답,,) 이 문제는 여러 그래프 집합으로 나뉘지 않고 이미 사용한 게이트 vs 사용 가능한 게이트 이 둘로만 나뉜다. -> 그럼 이미 사용한 게이트 = -1, 사용 가능한 게이트 = 자기자신 으로 설정하기 parent[i] == i 이면 parent[i] = -1로 바꿔주기 parent[i] != i 이면 parent[j] != -1 (j==i보다 작은 수들의 집합) 인 j중 최댓값 바뀐 풀이 Union-Find 알고리즘이라고 생각하면 복잡했는데 다른 방식으로 생각하니까 더 이해하기 쉬웠다. 예제2) 로 이해하기 |노드번호| 1 | 2 | 3 | 4 | 5 |

worldicate

입력 각 파티에 한 사람이라도 진실을 아는 사람 이면, 곧 그 파티에 존재하는 모든 사람은 진실을 아는 사람. -> 각 파티 마다 입력 되는 사람 : 같은 그래프로 묶는다. 진실을 아는 사람과 같은 그래프에 있는지 파악한다. -> 같은 그래프로 묶는 건 union, 같은 그래프에 속해있는지 판별하는 건 find 를 이용한다.

wuchangs

두 노드가 같은 그래프에 속해있는지 확인하는 union-find 알고리즘 활용해 풀었다.

pds0309

백준 4386 별자리 만들기 문제 >도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. >별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오. 문제 요약 2차원 좌표를 여러개 주는데 최소한의 비용으로 모두 이어야 한다. 풀이 과정 존재하는 모든 노드들을 최소한의 비용으로 모두 연결해야 하는 최소 신장 트리 문제이다. 단 노드와 노드간 거리가 직접 수치로 주어지는 것이 아니라 노드 하나에 대한 2차원 좌표가

babnbabn

문제 https://www.acmicpc.net/problem/3108 풀이 우선 입력받은 사각형은 bord에 1로 마크한다. 그리고 BFS를 이용해서 한붓으로 그릴 수 있는 사각형들을 체크한다. 몇번 BFS에 들어가는지가 중요하다. (0,0)에 있는 사각형이 있다면 1을 빼줘야 한다. 코드

hsh111366

https://www.acmicpc.net/problem/1774 > ### 문제 황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 이러던 와중에 새로운 우주신들이 황선자씨를 이용하게 되었다. 하지만 위대한 우주신들은 바로 황선자씨와 연결될 필요가 없다. 이미 황선자씨와 혹은 이미 우주신끼리 교감할 수 있는 우주신들이 있기 때문에 새로운 우주신들은 그 우주신들을 거쳐서 황선자 씨와 교감을 할 수 있다. 우주신들과의 교감은 우주신들과 황선자씨 혹은 우주신들 끼리 이어진 정신적인 통로를 통해 이루어 진다. 하지만 우주신들과 교감하는 것은 힘든 일이기 때문에 황선자씨는 이런 통로들이 긴 것을 좋아하지 않는다. 왜냐하면 통로들이 길 수록 더 힘이 들기 때문이다. 또한 우리들은 3차원 좌표계로 나타낼 수 있는 세상에 살고 있지만 우주신들과 황선자씨는 2차원 좌표계로 나타낼 수 있

hsh111366

https://www.acmicpc.net/problem/6497 > ### 문제 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다. 그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다. 위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오. > ### 입력 입력은 여러 개의 테스트 케이스로 구분되어 있다. 각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000) 이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에

hsh111366

https://www.acmicpc.net/problem/4386 > ### 문제 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오. > ### 입력 첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100) 둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다. > ### 출력 첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다. > ### 예제 ![](h

hsh111366

https://www.acmicpc.net/problem/1647 > ### 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이에 경로가 항상 존재한다. 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다. 그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된

hsh111366

https://www.acmicpc.net/problem/1043 > ### 문제 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다. 사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는