[백준 4195] - 친구 네트워크

 

문제

• 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다.
  • 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.
• 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
  • 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

 

입력

• 첫째 줄에 테스트 케이스의 개수가 주어진다.
  • 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다.
• 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다.
  • 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

 

출력

• 친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

 

 

솔루션

• Disjoint Set을 이용하는 문제이다.
  • 다만, 한 가지 추가로 생각해야 될 것은 입력으로 노드 숫자가 아니라 문자열 이름으로 주어졌다는 것이다.
    • 따라서 Map을 이용하여 이름을 Key 값으로 사용하고, 노드 숫자 (인덱스) 를 Value 값으로 사용한다. (Key-Value Pair)
  • 그리고 합집합 연산을 수행하면서 친구 관계 수도 구해준다.
• 아래 그림 예시를 통해 간단하게 확인해보자.

예시 1

예시 2

 

Code

• 전체코드 : Solution_4195

노드가 속한 집합의 루트를 반환해주는 함수

public static int Find(int u) {
    if (parent[u] == u)
        return u;
 
    return parent[u] = Find(parent[u]);
}

 

두 노드가 속한 집합을 합쳐주는 합집합 연산 (+ 관계 수 [집합내 노드 갯수] 까지 계산)

public static void Union(int u, int v) {
    int uR = Find(u);
    int vR = Find(v);
 
    if (uR == vR)
        return;
 
    if (rank[uR] > rank[vR])
        Swap(uR, vR);
 
    parent[uR] = vR;
    relation[vR] += relation[uR];
 
    if (rank[uR] == rank[vR])
        rank[vR]++;
}

 

메인 함수

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
    int testcase = Integer.parseInt(br.readLine());
 
    for (int i = 0; i < testcase; i++) {
        int F = Integer.parseInt(br.readLine());
        int idx = 0;
        list = new HashMap<>();
        parent = new int[MAX];
        rank = new int[MAX];
        relation = new int[MAX];
        
        Arrays.fill(relation, 1);
 
        for (int j = 0; j < F; j++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String name1 = st.nextToken();
            String name2 = st.nextToken();
 
            if(!list.containsKey(name1)) {
                list.put(name1, idx);
                parent[idx] = idx++;
            }
            
            if(!list.containsKey(name2)) {
                list.put(name2, idx);
                parent[idx] = idx++;
            }
 
            Union(list.get(name1), list.get(name2));
            
            bw.write(relation[Find(list.get(name1))] + "\n");
        }
    }
 
    bw.flush();
    bw.close();
    br.close();
}

 

결과