풀이
입력받은 이름에 대해 공통 부모를 갱신하며, 집합의 크기를 출력해야 되는 문제다.
공통 부모와, 집합의 크기를 저장할 parents, count 배열을 선언해주자.
문제에서 입력받은 친구 관계 F에 대해 입력받은 이름의 수는 최대 2F가 될 것이다.
때문에 위에서 선언한 배열의 크기 또한 2F로 할당받아야 한다.
모든 집합은 자기 자신에 대해 크기가 1이기에 count 배열은 1로 초기화 해주면 된다.
알다시피 parents 배열은 int형을 저장하는 배열이다.
때문에 입력받은 String형에 대해서는 Disjoint Set 구현이 불가능하다.
또한, parents 배열의 초깃값 설정을 할 때 자기 자신의 번호로 초기화를 해야하므로 String형 parent로 선언한다 하더라도 입력을 모두 받은 후 다시 한 번 입력값을 살펴봐야 하므로 비효율적이다.
메모리 제한은 넉넉하니 입력받은 이름을 번호로 매칭시켜줄 Hash Map을 선언해주자.
처음 입력받은 이름 이라면 이름과 순서를 등록시킬 것이다.
입력 예제 1을 예시로 설명한다면
Fred Barney
Barney Betty
Betty Wilma
일 때
<"Fred", 0>, <"Barney", 1>, <"Betty", 3>, <"Wilma", 4> 이다.
이제 String형 이름을 int형으로 매칭시켜줬으니 친구 관계를 갱신해주자.
친구 관계를 갱신해주며 갱신된 친구 관계에 대해 연결된 친구들의 수 즉 집합의 크기를 출력해야 한다.
매번 갱신할 때마다, 번호가 작은 친구에 대해 번호가 큰 친구와 연결할 수 있는 친구 수를 더해주어 갱신하고,
그 값을 출력하면 된다.
소스코드
출처
4195번: 친구 네트워크
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 20040] 사이클 게임 [Java] (0) | 2023.07.02 |
|---|---|
| [백준 4375] 1 [Java] (0) | 2023.06.29 |
| [백준 1976] 여행 가자 [Java] (0) | 2023.06.29 |
| [백준 17352] 여러분의 다리가 되어 드리겠습니다! [Java] (0) | 2023.06.29 |
| [백준 1717] 집합의 표현 [Java] (0) | 2023.06.28 |