# DisjointSet

16개의 포스트
post-thumbnail

[백준 - 1043] 거짓말

문제링크

2022년 2월 28일
·
0개의 댓글
post-thumbnail

BJ_4792 레드블루 스패닝 트리

BJ_4792Disjoint set 문제를 공부하는 중이다. 제법 simple한 방법이라고 생각하는 응용 범위가 넓고 정형화 되어 있지 않아 제법 어려운 문제들이 많이 등장한다. disjoint_set으로 문제를 계속 풀어가다가 발견한 이문제, 뭔가 disjoint_

2022년 2월 8일
·
0개의 댓글

유니온 파인드 구조

1. 유니온 파인드 구조 개념 2. 유니온 파인드 구조를 위한 세 가지 함수 > 1. 초기화 부모를 찾는다. 두 트리를 합친다. 3. 관련 코드

2022년 1월 6일
·
0개의 댓글

백준 10775번: 공항

백준 10775번: 공항기본적인 아이디어는 Greedy하게 남은 게이트 중 가장 번호가 큰 게이트에 도킹시키면 된다. 4를 입력받은 경우 4번 게이트가 남아있으면 4번, 없으면 3번, 3번도 없으면 2번.. 이런식으로 도킹하면 최대한 많이 도킹할 수 있다. 그런데 매번

2021년 11월 27일
·
0개의 댓글

백준 17398번: 통신망 분할

백준 17398번: 통신망 분할완성 상태에서 하나씩 끊어보면서 찾으면 10만 \* 10만이라 풀 수 없다.맨 처음에, 제거될 예정인 연결은 빼고 union한다. 그리고 입력받은 역순으로 연결하면서 비용을 더해준다.비용이 int 범위를 넘어갈 수 있기 때문에 long l

2021년 11월 26일
·
0개의 댓글

백준 9938번: 방 청소

백준 9938번: 방 청소서랍끼리 union 연산을 수행한다. 이 때 루트에는 연결된 서랍들중에 빈자리가 몇개인지 음수로 표시한다.이렇게 하면 술병을 입력받을 때마다 이 술을 보관할 수 있는지, 아니면 마셔야 하는지 알 수 있다.보관할 수 있다면 (입력받은 서랍 두개의

2021년 11월 26일
·
0개의 댓글

백준 11085번: 군사 이동

백준 11085번: 군사 이동C랑 V랑 연결시키는데 이 때 연결한 길의 w중 최소가 가장 큰 경우를 구하려고 한다. 즉 빙빙 돌아가도 상관 없으니 한번에 군사를 많이 이동하려면 어떻게 해야하는가? 를 묻는 문제다.간선을 w순으로 정렬하고 w가 큰 간선부터 union 연

2021년 11월 25일
·
0개의 댓글

백준 3197번: 백조의 호수

백준 3197번: 백조의 호수문명 문제랑 완전 똑같다. 문명이 퍼지는 대신 물이 퍼진다. 퍼질때마다 상하좌우 확인해서 물 있으면 Union, 연도 바뀌면 find. 사실 year가 아니라 day긴 함 ㅋㅋ;맨 처음에 물이랑 백조 싹다 큐에 넣으면서 상하좌우에 물이나 백

2021년 11월 25일
·
0개의 댓글

백준 14868번: 문명

백준 14868번: 문명상하좌우 한 칸씩 문명이 전파되는건 bfs로 어렵지 않게 구현할 수 있다. 숫자 1씩 늘리면서 몇년 지난건지도 알 수 있다. 그리고 방금 전파된 장소에서 상하좌우에 다른 문명이 있는 경우, union한다. 연도 순서대로 큐에 들어가기 때문에 1년

2021년 11월 25일
·
0개의 댓글

백준 2162번: 선분 그룹

백준 2162번: 선분 그룹선분이 교차하면 Union.유니온 파인드 자료구조에서 proot에는 원소의 개수(음수로) 저장.백준 4195번: 친구 네트워크백준 17387번: 선분 교차 2여기서 둘 다 자세하게 설명했으니 따로 적진 않겠다. 알아야 하는 개념이 좀 많다.

2021년 11월 22일
·
0개의 댓글

백준 4195번: 친구 네트워크

백준 4195번: 친구 네트워크유니온 파인드 자료구조에 잡기술을 하나 추가한다. 원래 parentn == n 이면 루트 노드임을 확인하고 n을 리턴했는데 대신에 parentn이 음수인 경우 루트 노드임을 확인하고 n을 리턴해준다. 기본적으로 모두 -1을 가지고 있고

2021년 11월 19일
·
0개의 댓글

백준 16562번: 친구비

백준 16562번: 친구비친구끼리 Union해주는데 이 때 친구비가 제일 저렴한 애가 루트가 되도록 합친다.맨 처음에는 cost루트 인덱스에 각 집합의 최소 친구비가 들어가도록 짰는데 잘 안됐다. 왜안됐지? 솔직히 아직도 잘 모르겠다. 이렇게 했는데 어딘가 빼먹는게 있

2021년 11월 19일
·
4개의 댓글

백준 1717번: 집합의 표현

백준 1717번: 집합의 표현유니온 파인드 (분리 집합)이라고 부르는 자료구조가 있다.각 원소는 모두 트리의 루트이고, 이를 합치는 연산(union)과 루트를 확인하는 연산(find) 두가지가 존재한다. 원래는 parent에 자기 부모를 저장해서 주루루룩 타고 올라

2021년 11월 19일
·
0개의 댓글
post-thumbnail

친구인가

Greedy

2021년 8월 30일
·
0개의 댓글
post-thumbnail

자료구조_Disjoint Set

분리집합/서로소집합/UnionFind

2020년 11월 26일
·
0개의 댓글

Disjoint Set / Union Find 이란?

Disjoint set과 Union Find에 대하여

2020년 7월 4일
·
0개의 댓글