반응형
SMALL
SW Expert Acadmey D4
-
SW Expert Academy D4 문제 풀이 (1)알고리즘 2023. 7. 4. 16:42
7465. 창용 마을 무리의 개수 N명의 사람에 대해서 두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면 이러한 사람들을 모두 다 묶어서 하나의 무리라고 합니다. 서로를 알고 있는 사람의 관계가 주어질 경우 해당 마을의 무리의 개수를 구하는 문제입니다. 이 문제는 각 노드마다 부모 노드를 지정해주고, 같은 부모 노드를 가리키는 노드들은 같은 무리로 지칭하는 유니온 파인드(Union-Find)를 활용하여 문제를 풀었습니다. parent[N+1] 배열의 모든 원소를 자신의 인덱스로 지정해줍니다. int[] parent = new int[N+1]; for(int i=0;i