728x90
🔗 문제링크 🔗
4195번: 친구 네트워크
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진
www.acmicpc.net
🌟 생각 흐름 🌟
두 친구에 대한 이름에 대한 저장이 필요해서 HashMap을 이용해서 이름과 배열에 할당할 index를 저장했다.
배열의 사이즈는 n개의 라인에 모두 서로 다른 친구가 나올 수 있을 것 같아 2*n으로 할당했다.
이후에는 친구의 이름이 해시에 없다면 저장하고 있다면 찾아온다.(만약 그냥 저장하면 index번호가 꼬이므로 저장하지 않는다)
두 친구가 이미 친구 관계인 경우에는 친구의 개수를 리턴하고 친구가 아닌 경우에만 union을 진행한다
union을 하는 경우에 두 사람중의 부모 중에 index가 낮은 곳에 다른 친구 수를 더하여 저장하고 찾은 부모 인덱스 중에 더 작은 인덱스를 리턴하도록 하여 바로 Main에서 친구 수를 출력하도록 하였다.
이것이 가능한 이유는 모든 union을 할때마다 친구들 중에 작은 index를 가진 친구에게 저장할 것이고 이후에 자신의 친구 중 index가 가장 작은(findParent를 통해 나온 index)의 친구수를 이용하면 풀 수 있기 때문에 가능하다.
🍳 코드 🍳
728x90
'알고리즘' 카테고리의 다른 글
| [백준 Java] 16397 탈출 BFS 골드 4 (0) | 2023.03.19 |
|---|---|
| [백준 Java] 1946 신입사원 실버1 , 그리디 (0) | 2023.03.09 |
| [백준 Java]15711_환상의 짝궁_수학, 소수 (0) | 2023.02.25 |
| [백준 Java]1459_걷기_그리디 (0) | 2023.02.23 |
| [백준]1953_팀배분_DFS(BFS도 가능) (0) | 2023.02.22 |
댓글