# DisjointSet
BJ_4792 레드블루 스패닝 트리
BJ_4792Disjoint set 문제를 공부하는 중이다. 제법 simple한 방법이라고 생각하는 응용 범위가 넓고 정형화 되어 있지 않아 제법 어려운 문제들이 많이 등장한다. disjoint_set으로 문제를 계속 풀어가다가 발견한 이문제, 뭔가 disjoint_
유니온 파인드 구조
1. 유니온 파인드 구조 개념 2. 유니온 파인드 구조를 위한 세 가지 함수 > 1. 초기화 부모를 찾는다. 두 트리를 합친다. 3. 관련 코드
백준 10775번: 공항
백준 10775번: 공항기본적인 아이디어는 Greedy하게 남은 게이트 중 가장 번호가 큰 게이트에 도킹시키면 된다. 4를 입력받은 경우 4번 게이트가 남아있으면 4번, 없으면 3번, 3번도 없으면 2번.. 이런식으로 도킹하면 최대한 많이 도킹할 수 있다. 그런데 매번
백준 17398번: 통신망 분할
백준 17398번: 통신망 분할완성 상태에서 하나씩 끊어보면서 찾으면 10만 \* 10만이라 풀 수 없다.맨 처음에, 제거될 예정인 연결은 빼고 union한다. 그리고 입력받은 역순으로 연결하면서 비용을 더해준다.비용이 int 범위를 넘어갈 수 있기 때문에 long l
백준 9938번: 방 청소
백준 9938번: 방 청소서랍끼리 union 연산을 수행한다. 이 때 루트에는 연결된 서랍들중에 빈자리가 몇개인지 음수로 표시한다.이렇게 하면 술병을 입력받을 때마다 이 술을 보관할 수 있는지, 아니면 마셔야 하는지 알 수 있다.보관할 수 있다면 (입력받은 서랍 두개의
백준 11085번: 군사 이동
백준 11085번: 군사 이동C랑 V랑 연결시키는데 이 때 연결한 길의 w중 최소가 가장 큰 경우를 구하려고 한다. 즉 빙빙 돌아가도 상관 없으니 한번에 군사를 많이 이동하려면 어떻게 해야하는가? 를 묻는 문제다.간선을 w순으로 정렬하고 w가 큰 간선부터 union 연
백준 3197번: 백조의 호수
백준 3197번: 백조의 호수문명 문제랑 완전 똑같다. 문명이 퍼지는 대신 물이 퍼진다. 퍼질때마다 상하좌우 확인해서 물 있으면 Union, 연도 바뀌면 find. 사실 year가 아니라 day긴 함 ㅋㅋ;맨 처음에 물이랑 백조 싹다 큐에 넣으면서 상하좌우에 물이나 백
백준 14868번: 문명
백준 14868번: 문명상하좌우 한 칸씩 문명이 전파되는건 bfs로 어렵지 않게 구현할 수 있다. 숫자 1씩 늘리면서 몇년 지난건지도 알 수 있다. 그리고 방금 전파된 장소에서 상하좌우에 다른 문명이 있는 경우, union한다. 연도 순서대로 큐에 들어가기 때문에 1년
백준 2162번: 선분 그룹
백준 2162번: 선분 그룹선분이 교차하면 Union.유니온 파인드 자료구조에서 proot에는 원소의 개수(음수로) 저장.백준 4195번: 친구 네트워크백준 17387번: 선분 교차 2여기서 둘 다 자세하게 설명했으니 따로 적진 않겠다. 알아야 하는 개념이 좀 많다.
백준 4195번: 친구 네트워크
백준 4195번: 친구 네트워크유니온 파인드 자료구조에 잡기술을 하나 추가한다. 원래 parentn == n 이면 루트 노드임을 확인하고 n을 리턴했는데 대신에 parentn이 음수인 경우 루트 노드임을 확인하고 n을 리턴해준다. 기본적으로 모두 -1을 가지고 있고
백준 16562번: 친구비
백준 16562번: 친구비친구끼리 Union해주는데 이 때 친구비가 제일 저렴한 애가 루트가 되도록 합친다.맨 처음에는 cost루트 인덱스에 각 집합의 최소 친구비가 들어가도록 짰는데 잘 안됐다. 왜안됐지? 솔직히 아직도 잘 모르겠다. 이렇게 했는데 어딘가 빼먹는게 있
백준 1717번: 집합의 표현
백준 1717번: 집합의 표현유니온 파인드 (분리 집합)이라고 부르는 자료구조가 있다.각 원소는 모두 트리의 루트이고, 이를 합치는 연산(union)과 루트를 확인하는 연산(find) 두가지가 존재한다. 원래는 parent에 자기 부모를 저장해서 주루루룩 타고 올라
