Post List

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

날짜:

 BOJ 4195 친구 네트워크



지금까지 Union Find 문제에서 입력은 정수 였습니다.
하지만 이 문제에서는 입력을 정수가 아닌 문자열로 받았습니다.
따라서 저는 Map 을 이용하여 문자열을 key로, 정수를 value로 잡았습니다.
Map에서 문자열(이름)은 바뀌지 않습니다. 그리고 map의 value 와 Union 되었는지를 판단하는 벡터가 value로 연동되어 일반적인 Union Find 함수를 사용할 수 있습니다.

특이사항으로, 전역변수로 설정한 vector, map을 매 테스트 케이스마다 리셋 해주어야 했습니다. 저는 벡터를 선언할 때 100001개로 설정을 했는데, vector.clear()를 사용하면
size를 0으로 만들어 버립니다. 따라서 clear 대신 fill을 사용하였습니다.

소스코드 :

#include 
#include 
#include 
#include 
using namespace std;


vector v(100001);
vector vsize(100001, 1);
map m;

// 일반적인 Union - Find 함수
int Find(int p) {
 if (p == v[p]) return p;
 return v[p] = Find(v[p]);
}
void Union(int p1, int p2) {
 int node1 = Find(p1);
 int node2 = Find(p2);
 if (vsize[node1] > vsize[node2]) swap(node1, node2);
 if (node1 != node2) {
  vsize[node2] += vsize[node1];
  vsize[node1] = 0;
  v[node1] = v[node2];
 }
 // 어차피 Node2가 주축이 되는 노드이므로 인간관계의 개수는 node2의 사이즈임.
 cout << vsize[node2] << '\n';
}

int main() {
 ios_base::sync_with_stdio(0);
 cin.tie(0);

 int N;
 cin >> N;
 for (int i = 0; i < N; i++) {
  int F;
  cin >> F; cin.ignore();
  int network = 0;
  for (int j = 0; j < F; j++) {
   string s1;
   cin >> s1; cin.ignore();
   // Map에 이름(string) 이 없을경우 추가.
   if (m.find(s1) == m.end()) {
    v[network] = network;
    vsize[network] = 1;
    m.insert({s1, network++});
   }
   string s2;
   cin >> s2; cin.ignore();
   if (m.find(s2) == m.end()) {
    v[network] = network;
    vsize[network] = 1;
    m.insert({ s2, network++ });
   }   
   Union(m.find(s1)->second, m.find(s2)->second);
  }
  // 이미 100001개로 벡터의 크기를 지정했으므로 clear 대신 fill 사용.
  fill(v.begin(), v.begin() + 100001, 0);
  fill(vsize.begin(), vsize.begin() + 100001, 1);
  m.clear();
 }
}

댓글

댓글 쓰기