[C++]백준 - 4195번 문제

4195번: 친구 네트워크 (acmicpc.net)

4195번: 친구 네트워크

 

4195번 : 친구 네트워크

---

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

 

입력

---

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

 

 

출력

---

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

 

 

 

---

 

생각해 볼 점

---

문제가 잘 이해가 되지 않았습니다만, 문제를 잘 읽어보면..

 

'친구 관계를 새로 받을 때마다, 해당 친구 네트워크에 몇 명이 있는 지 확인해달라'는 뜻입니다.

 

예를들어, Fred Barney를 받았다면, Fred Barney가 속한 친구 네트워크가 몇 명인지 출력하면 됩니다.

 

유니온을 만들고, 그 유니온이 몇 명을 포함하는 지 확인할 배열(Rank)을 추가 합니다.

 

Parent[A] = A, Rank[A] = 1,

Parent[B] = B, Rank[B] = 3

 

Union (A, B) -> Parent[A] = B, Rank[B] = Rank[B] + Rank[A]

 

위와 같은 과정을 거치면 될 것 같습니다.

 

코드

---

#include <iostream>
#include <map>
using namespace std;

//부모를 찾는 함수
int find_parent(int parent[], int A)
{
    while(A != parent[A]) A = parent[A];
    return A;
}

//유니온을 만들고, 유니온의 크기를 반환하는 함수
int set_union(int parent[], int rank[], int A, int B)
{
    A = find_parent(parent, A);
    B = find_parent(parent, B);
    
    if(A == B) return rank[A];
    if(rank[A] < rank[B]) 
    {
        parent[A] = B;
        rank[B] += rank[A];
        return rank[B];
    }
    else
    {
        parent[B] = A;
        rank[A] += rank[B];
        return rank[A];
    }
}


int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	int TC;
	cin >> TC;
	
	for(int t = 0; t < TC; t++)
	{
	    int N;
	    cin >> N;
	    
	    map<string, int> hash;       //이름 : index
	    int *parent = new int[N * 2];   
	    int *rank = new int[N * 2];     //유니온의 크기를 담음
	    
	    for(int i = 0; i < N * 2; i++) parent[i] = i;
	    fill_n(rank, N * 2, 1);

	    int index = 0;
	    for(int i = 0; i < N; i++)
	    {
	        string A, B;
	        cin >> A >> B;
	        
	        if(hash.find(A) == hash.end()) 
	        {
	            hash.insert({A, index});
	            index++;
	        }
	        if(hash.find(B) == hash.end())
	        {
	            hash.insert({B, index});
	            index++;
	        }
	        
	        int ret = set_union(parent, rank, hash.find(A)->second, hash.find(B)->second);

	        cout << ret << "\n";
	    }
	    
	    delete[] parent;
	    delete[] rank;
	}
	
	return 0;
}

 

그 외

---