[BOJ] 백준 4195 친구 네트워크 (JAVA)

HashMap + unionFind

📑 문제

 

백준 4195 친구 네트워크

---

🌱 아이디어

위 문제에서 친구가 된 순서의 정보를 차례차례 제공한다.

그렇다면 단계마다 해당 친구가 속한 네트워크(집합)의 크기를 구하는 문제이다!

 

크게 생각해야 하는 점은 두 가지가 있다.

1. 친구의 정보가 이름(문자열)으로 제공되는 점
2. 친구 네트워크(집합)에 속한 크기를 구하는 방법.

 

1번의 경우는

HashMap을 사용하여 key : 이름 -> value : 번호로 치환해서 유니온파인드 알고리즘을 실행하면 된다.

당연히 해쉬맵에 이름이 있는지 판단해야 하고. 없다면 번호를 부여한다.

 

2번의 경우는

유니온 파인드 알고리즘을 사용하고 그중 union 함수에서

 

두 노드의 부모노드가 다르다면? -> 서로 다른 노드임 -> 친구가 되었기 때문에 ans [부모노드] += ans [자식노드]로 업데이트 후 출력

자식노드에 부모노드를 표시를 해준다, 즉 같은 친구네트워크 표시를 해준다.

 

두 노드의 부모노드가 같다면? -> 이미 같은 네트워크(집합) 임 -> 전에 합쳤기 때문에 그냥 출력 

 

이런 흐름으로 출력을 한다면 답을 구할 수 있다.

 

그리고 배열의 최대 크기를 200,000인 이유는

F == 100,000 인경우 친구 1, 친구 2 가 매번 다르다면 총 200,000의 친구(노드)가 생기기 때문이다.

---

🌱 코드 및 풀이

 

---

🌱 느낀 점

 

유니온 파인드 응용문제였다. 오랜만에 분리집합 문제를 풀었는데, 사실 전에 풀다가 포기한 문제였다.

그동안 다른 유형의 문제를 풀다 보니 풀 수 있게 되었다. 꾸준히 풀어보자