(JAVA) 백준 4195번 : 친구 네트워크

https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

 

 

처음에 Union - Find 알고리즘을 생각도 못하고 

 

정공법으로 풀려고 했으나

 

제한 시간과 여러 변수들이 많아 

 

어떤 알고리즘으로 풀어야했는지 검색했었다...

 

 

그 다음

 

Union - Find 알고리즘을 사용해서 정답은 유추했으나 시간 제한이 걸려버렸다. (심지어 3초인데도..)

 

그래서 이것저것 바꾸다가 알게된 사실은

 

HashMap이 탐색 시 가장 빠르다는 것.

 

 

필자는 처음 문자열과 그 문자열의 index를 넣기 위해 ArrayList를 사용했으나 

 

어차피 삽입 / 탐색 밖에 안하는 이 문자열과 index를 굳이 ArrayList를 사용했기 때문에

 

시간 초과가 발생했었다.

 

HashMap으로 변경하니 문제 해결!

*** LinkedHashMap을 사용해도 되지만, 어차피 value에 index를 넣기 때문에 상관이없다고 생각했다.

 

 

 

그렇지만

 

필자가 푼 해결방법은 시간이 넘나 소모되는 풀이였고..

 

그래서 베스트 해답을 참고해서 다시 풀었다.

 

 

 

이 해답의 풀이 방법을 간략히 적어보겠다.

 

 

 

  -  초기 모든 노드 값을 -1로 설정

 

  -  부모 노드는 음수로서 자식노드들의 크기를 담고 있고, 자식 노드들은 부모 노드의 인덱스를 가지고 있음

 

  -  둘 다 부모 노드일 경우 값 비교를 통해 절댓값이 작은 부모 노드를 큰 부모 노드에 이어붙인다.

  *** 절댓값이 작다는 뜻은 결국 네트워크 자식들의 개수가 작다는 것

  -  굳이 자식 노드들 전부 변경하지 않고 부모 노드만 한 번 바꿔놓으면 어차피 find 함수를 통해 최상단 부모 노드를 찾을 수 있음
 

  -  그래서 네트워크의 크기 계산까지 가능하게 됨

 

 

 

 

 

자세한 부분은 소스코드를 참고하시면 좋겠습니다.

 

 

감사합니다!

 

소스코드

---