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

문제

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

4195번: 친구 네트워크

민혁이는 소셜 네트워크에서 친구 만드는걸 좋아한다. 

어떤 사이트의 친구관계가 주어졌을때, 해당 친구관계에 포함되어있는 친구의 수를 출력하는 프로그램을 만드는 문제다.

 

---

풀이

친구관계가 최대 10만까지 갈수있으므로, 매 쿼리마다 모든 노드를 탐색하면, O(N^2)의 시간복잡도가나와 TLE를 받게된다.

문제를 풀기위해 유니온파인드를 사용해야했다.

 

문제의 노드정보가 문자열로 주어지기때문에, 일정한 방법으로 노드정보를 변경후 풀어야한다.

크게 두가지 방법을 생각해볼수있다.

 

1. 유니온파인드를 이용해 최적화 하며, 그래프 구조를 HashMap으로 직접적으로 표현하여 문자열끼리 이어준다.

예를들어, James, Alex, Betty 가 있다고하면,

James - Alex 

Alex - Betty

이런식으로 연결해주는 방법이 있다. 하지만, 이렇게 할경우, 유니온 파인드를 적용하기위해 자신의 최상단 부모노드를 찾는과정에서 모든 문자열을 탐색할수도 있기때문에, 시간이 너무 오래걸린다. (나는 이렇게 풀지 않아서 통과가 될지 안될지는 모른다.)

 

2. 유니온파인드를 이용해 최적화 하며, 그래프 구조를 기본적인 그래프구조로 표현한다.(par[1] = 2, par[2] = 3 이런 정수형으로)

이렇게 할경우, 매 탐색마다 O(1)만에 자신의 부모를 찾을수있다. 

이 방법을 사용하기 위해서 우선, HashMap을 사용해서 친구의 이름을 중복없는 특정한 숫자에 매핑해준다.

James = 1

Alex = 2

Betty = 3

(이런식으로)

 

나머지는 기본적인 유니온 파인드 최적화 하듯이 하면 된다.

 

유니온 파인드 코드

    private int findDisjointSet(int idx){
        if(disjointSet[idx] == idx) return idx;
        return disjointSet[idx] = findDisjointSet(disjointSet[idx]);
    }
    
    private int setDisjointSet(int par, int son){
        par = findDisjointSet(par);
        son = findDisjointSet(son);
        if(par != son){
            disjointSet[son] = par;
            friendsCount[par] += friendsCount[son];
        }
        return friendsCount[par];
    }

 

friendsCount를 구하는 방식을 보자.

우선 친구 1과 친구 2 (코드에서는 par과 son 으로 표현했다.) 가 같은 집합에 있는지 확인한다. (같은집합에 있다면, 이미 친구관계가 더해진것임.)

아니라면, 친구 1과 친구 2가 갖고있는 친구관계수를 더해준다. 

 

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/4195%20%EC%B9%9C%EA%B5%AC%20%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC/Main.java

devxb/JJUNalgo