DisjointSet 백준 2162번: 선분 그룹 선분이 교차하면 Union. 유니온 파인드 자료구조에서 p[root]에는 원소의 개수(음수로) 저장. 여기서 둘 다 자세하게 설명했으니 따로 적진 않겠다. 알아야 하는 개념이 좀 많다. 실전에서 이런거 문제로 나오면 시간없어서 못풀듯..... Union FindDisjointSetgeometrycpppsDisjointSet 백준 3197번: 백조의 호수 문명 문제랑 완전 똑같다. 문명이 퍼지는 대신 물이 퍼진다. 퍼질때마다 상하좌우 확인해서 물 있으면 Union, 연도 바뀌면 find. 사실 year가 아니라 day긴 함 ㅋㅋ; 맨 처음에 물이랑 백조 싹다 큐에 넣으면서 상하좌우에 물이나 백조 있으면 Union 해준다. 이거 정답률이 19퍼인데 다들 bfs dfs만 들이박다 시간초과가 나온 듯 하다.... Union FindpsBFScppDisjointSetBFS 백준 17398번: 통신망 분할 완성 상태에서 하나씩 끊어보면서 찾으면 10만 * 10만이라 풀 수 없다. 맨 처음에, 제거될 예정인 연결은 빼고 union한다. 그리고 입력받은 역순으로 연결하면서 비용을 더해준다. 비용이 int 범위를 넘어갈 수 있기 때문에 long long으로 선언해야한다. 이런 디테일이 부족한 것 같다.... Union FindDisjointSetpscppDisjointSet 백준 11085번: 군사 이동 C랑 V랑 연결시키는데 이 때 연결한 길의 w중 최소가 가장 큰 경우를 구하려고 한다. 즉 빙빙 돌아가도 상관 없으니 한번에 군사를 많이 이동하려면 어떻게 해야하는가? 를 묻는 문제다. 간선을 w순으로 정렬하고 w가 큰 간선부터 union 연산을 한다. 종료조건은 find(C) == find(V). 가장 최근 연결했던 간선의 w를 출력하면 정답! 문제 뭔소린지 이해 안돼서 한참 읽었다. 난 ... Union FindDisjointSetpscppDisjointSet BJ_4792 레드블루 스패닝 트리 Disjoint set 문제를 공부하는 중이다. 제법 simple한 방법이라고 생각하는 응용 범위가 넓고 정형화 되어 있지 않아 제법 어려운 문제들이 많이 등장한다. disjoint_set으로 문제를 계속 풀어가다가 발견한 이문제, 뭔가 disjoint_set으로만 풀기는 어렵다고 생각하면서도 열심히 풀었는데, 역시나 안되서 살펴보니 Kruskal's algorithm을 사용해야 하는 문제였... 시간초과Kruskal_AlgorithmDisjointSetminimumSpanningTreePopDisjointSet
백준 2162번: 선분 그룹 선분이 교차하면 Union. 유니온 파인드 자료구조에서 p[root]에는 원소의 개수(음수로) 저장. 여기서 둘 다 자세하게 설명했으니 따로 적진 않겠다. 알아야 하는 개념이 좀 많다. 실전에서 이런거 문제로 나오면 시간없어서 못풀듯..... Union FindDisjointSetgeometrycpppsDisjointSet 백준 3197번: 백조의 호수 문명 문제랑 완전 똑같다. 문명이 퍼지는 대신 물이 퍼진다. 퍼질때마다 상하좌우 확인해서 물 있으면 Union, 연도 바뀌면 find. 사실 year가 아니라 day긴 함 ㅋㅋ; 맨 처음에 물이랑 백조 싹다 큐에 넣으면서 상하좌우에 물이나 백조 있으면 Union 해준다. 이거 정답률이 19퍼인데 다들 bfs dfs만 들이박다 시간초과가 나온 듯 하다.... Union FindpsBFScppDisjointSetBFS 백준 17398번: 통신망 분할 완성 상태에서 하나씩 끊어보면서 찾으면 10만 * 10만이라 풀 수 없다. 맨 처음에, 제거될 예정인 연결은 빼고 union한다. 그리고 입력받은 역순으로 연결하면서 비용을 더해준다. 비용이 int 범위를 넘어갈 수 있기 때문에 long long으로 선언해야한다. 이런 디테일이 부족한 것 같다.... Union FindDisjointSetpscppDisjointSet 백준 11085번: 군사 이동 C랑 V랑 연결시키는데 이 때 연결한 길의 w중 최소가 가장 큰 경우를 구하려고 한다. 즉 빙빙 돌아가도 상관 없으니 한번에 군사를 많이 이동하려면 어떻게 해야하는가? 를 묻는 문제다. 간선을 w순으로 정렬하고 w가 큰 간선부터 union 연산을 한다. 종료조건은 find(C) == find(V). 가장 최근 연결했던 간선의 w를 출력하면 정답! 문제 뭔소린지 이해 안돼서 한참 읽었다. 난 ... Union FindDisjointSetpscppDisjointSet BJ_4792 레드블루 스패닝 트리 Disjoint set 문제를 공부하는 중이다. 제법 simple한 방법이라고 생각하는 응용 범위가 넓고 정형화 되어 있지 않아 제법 어려운 문제들이 많이 등장한다. disjoint_set으로 문제를 계속 풀어가다가 발견한 이문제, 뭔가 disjoint_set으로만 풀기는 어렵다고 생각하면서도 열심히 풀었는데, 역시나 안되서 살펴보니 Kruskal's algorithm을 사용해야 하는 문제였... 시간초과Kruskal_AlgorithmDisjointSetminimumSpanningTreePopDisjointSet