tose33

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 키워드는 두 가지다. 해쉬맵, 유니온. 일단 이름이 문자열로 주어져서 머리 아플수 있는데 그냥 해쉬맵에 각 이름을 key로 value에 번호를 각각 부여해서 문자열은 생각하지 말고 번호로 생각한다. 이제 두 사람이 주어질때 두 노드가 주어진다고 생각하면 된다. 두 노드를 연결했을때 두 노드가 속한 그래프의 노드의 수를 구하면 되는 것인데, Union-Find 알고리즘을 쓰면 된다. 다른..

https://m.blog.naver.com/PostView.naver?blogId=ndb796&logNo=221230967614&referrerCode=0&searchKeyword=union 17. Union-Find(합집합 찾기) Union-Find(유니온-파인드)는 대표적인 그래프 알고리즘입니다. 바로 '합집합 찾기'라는 의미를 가진 알... blog.naver.com (위 안경잡이개발자 님의 블로그를 보고 공부했습니다.) Union-Find 알고리즘은 이름 그대로 union(합하고), Find(찾는) 알고리즘이다. 서로소 집합 (Disjoint-set) 알고리즘이라고도 불리는데, 두 노드를 선택했을때 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이기 때문이다. 알고리즘이 작동하는 방식은 다음..