DisjointSet 백준 2162번: 선분 그룹 선분이 교차하면 Union. 유니온 파인드 자료구조에서 p[root]에는 원소의 개수(음수로) 저장. 여기서 둘 다 자세하게 설명했으니 따로 적진 않겠다. 알아야 하는 개념이 좀 많다. 실전에서 이런거 문제로 나오면 시간없어서 못풀듯..... Union FindDisjointSetgeometrycpppsDisjointSet 백준 3197번: 백조의 호수 문명 문제랑 완전 똑같다. 문명이 퍼지는 대신 물이 퍼진다. 퍼질때마다 상하좌우 확인해서 물 있으면 Union, 연도 바뀌면 find. 사실 year가 아니라 day긴 함 ㅋㅋ; 맨 처음에 물이랑 백조 싹다 큐에 넣으면서 상하좌우에 물이나 백조 있으면 Union 해준다. 이거 정답률이 19퍼인데 다들 bfs dfs만 들이박다 시간초과가 나온 듯 하다.... Union FindpsBFScppDisjointSetBFS 백준 10775번: 공항 기본적인 아이디어는 Greedy하게 남은 게이트 중 가장 번호가 큰 게이트에 도킹시키면 된다. 4를 입력받은 경우 4번 게이트가 남아있으면 4번, 없으면 3번, 3번도 없으면 2번.. 이런식으로 도킹하면 최대한 많이 도킹할 수 있다. 그런데 매번 입력받을 때마다 g(i)번부터 1번까지 자리가 있나 탐색을 할 수는 없는 노릇이다. 10만 * 10만이라 시간초과임. 유니온 파인드 자료구조를 통해... Union FindDisjointSetpscppDisjointSet 백준 17398번: 통신망 분할 완성 상태에서 하나씩 끊어보면서 찾으면 10만 * 10만이라 풀 수 없다. 맨 처음에, 제거될 예정인 연결은 빼고 union한다. 그리고 입력받은 역순으로 연결하면서 비용을 더해준다. 비용이 int 범위를 넘어갈 수 있기 때문에 long long으로 선언해야한다. 이런 디테일이 부족한 것 같다.... Union FindDisjointSetpscppDisjointSet
백준 2162번: 선분 그룹 선분이 교차하면 Union. 유니온 파인드 자료구조에서 p[root]에는 원소의 개수(음수로) 저장. 여기서 둘 다 자세하게 설명했으니 따로 적진 않겠다. 알아야 하는 개념이 좀 많다. 실전에서 이런거 문제로 나오면 시간없어서 못풀듯..... Union FindDisjointSetgeometrycpppsDisjointSet 백준 3197번: 백조의 호수 문명 문제랑 완전 똑같다. 문명이 퍼지는 대신 물이 퍼진다. 퍼질때마다 상하좌우 확인해서 물 있으면 Union, 연도 바뀌면 find. 사실 year가 아니라 day긴 함 ㅋㅋ; 맨 처음에 물이랑 백조 싹다 큐에 넣으면서 상하좌우에 물이나 백조 있으면 Union 해준다. 이거 정답률이 19퍼인데 다들 bfs dfs만 들이박다 시간초과가 나온 듯 하다.... Union FindpsBFScppDisjointSetBFS 백준 10775번: 공항 기본적인 아이디어는 Greedy하게 남은 게이트 중 가장 번호가 큰 게이트에 도킹시키면 된다. 4를 입력받은 경우 4번 게이트가 남아있으면 4번, 없으면 3번, 3번도 없으면 2번.. 이런식으로 도킹하면 최대한 많이 도킹할 수 있다. 그런데 매번 입력받을 때마다 g(i)번부터 1번까지 자리가 있나 탐색을 할 수는 없는 노릇이다. 10만 * 10만이라 시간초과임. 유니온 파인드 자료구조를 통해... Union FindDisjointSetpscppDisjointSet 백준 17398번: 통신망 분할 완성 상태에서 하나씩 끊어보면서 찾으면 10만 * 10만이라 풀 수 없다. 맨 처음에, 제거될 예정인 연결은 빼고 union한다. 그리고 입력받은 역순으로 연결하면서 비용을 더해준다. 비용이 int 범위를 넘어갈 수 있기 때문에 long long으로 선언해야한다. 이런 디테일이 부족한 것 같다.... Union FindDisjointSetpscppDisjointSet