[백준] No.4195 - 친구 네트워크 (C++, 분리 집합)

문제

 

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

4195번: 친구 네트워크

 

 

풀이

 

solved.ac 난이도: Gold 2

 

 

Union-Find(유니온 파인드)에 map자료구조를 적용하면 간단히 해결할 수 있는 분리 집합(DisJoint Set) 문제였다.

 

분리 집합을 구현하는 데 사용하는 기본적인 Union-Find(유니온 파인드) 자료구조에 대해서는 아래의 게시글을 참고하자.

유니온-파인드(Union-Find), 분리 집합

 

이번 문제에서는 노드의 번호가 아닌 유저의 ID가 대신 주어진다.

문자열들로 자신의 부모를 저장해 두기는 구현이 복잡해질 수 있으니, map자료 구조를 활용해서 문자열로 주어지는 ID를 숫자 번호로 바꿔주자.

map자료구조는 탐색에 O(logN)의 시간 복잡도가 소요되므로 ID에 해당하는 번호를 빠르게 찾을 수 있다.

 

만약 네트워크를 찾는 두 개의 ID 중에 입력에서 처음 등장하는 ID가 있다면 새로 map에 삽입하며 해당 id의 번호는 중복을 방지하기 위해 현재 map의 크기로 한다.

이를 구현한 Union함수는 다음과 같다.

 

int Union(string u, string v){
  map<string,int>::iterator u_it,v_it;
 
  u_it = id_map.find(u);
  if(u_it == id_map.end()){//u가 map에 존재하는지
    id_map.insert( make_pair(u,id_map.size()));
    u_it = id_map.find(u);
  }
 
  v_it = id_map.find(v);
  if(v_it == id_map.end()){/v가 map에 존재하는지
    id_map.insert( make_pair(v,id_map.size()));
    v_it = id_map.find(v);
  }
  int u_idx = u_it->second, v_idx = v_it->second;
 
  u_idx = Find(u_idx), v_idx = Find(v_idx);
  if(u_idx == v_idx)
    return set_size[v_idx];
    
  if(rank[v_idx]<rank[u_idx])
    swap(u_idx, v_idx);
    
  parent[u_idx] = v_idx;
  set_size[v_idx] += set_size[u_idx];
 
  if(rank[v_idx] == rank[u_idx])
    rank[v_idx]++;
 
  return set_size[v_idx];
}

 

추가적으로 두 ID의 집합을 합친 후의 해당 집합의 크기를 반환해주기 위해

집합의 노드의 set_size에는 집합의 크기(원소 수)를 저장해주자.

위의 코드에서는 항상 v의 집합에 u의 집합을 합치므로 v의 하위로 들어오는 u집합의 크기를 v집합의 크기에 더해준다.

set_size[v_idx] += set_size[u_idx]

 

 

해당 문제에서는 입출력이 많기 때문에 iostream의 입출력 함수로는 시간 초과가 발생한다.

이런 문제에서는 cstdio의 입출력 함수를 사용하자.

 

코드