union find1 [백준/C++] #4195 친구 네트워크 (Union Find) 문제https://www.acmicpc.net/problem/4195 구상친구 관계가 주어지고, 친구 네트워크에 몇 명이 있는지 구해내는 문제였다. 그래서 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하는 Disjoint Set 자료구조를 사용해야겠다 싶었고, Disjoint Set를 표현하기 위해서 Union Find 알고리즘을 사용해야했다. Union Find에서 집합(네트워크)을 구현할 때 벡터, 배열, 맵 등의 자료구조를 이용할 수 있는데, 나는 unordered map을 선택했다. 처음에 벡터를 이용하는 방식으로 구현했었는데, 불필요하게 벡터의 크기가 커졌다. 그래서 네트워크를 표현하는 딱 필요한 연결리스트만 표현하기 위해서는 map을 사용하면 좋겠다는 생각이 들었고, 데이.. 2024. 8. 28. 이전 1 다음
