친구 네트워크

알고리즘 구분 : 자료 구조, 유니온 파인드, 해시 테이블

문제

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

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

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

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

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

예제 입력 1
2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty
예제 출력 1
2
3
4
2
2
4

문제 풀이

처음 문제를 보았을 때, 유니온 파인드 문제이기에, 어려움이 없을 것이라 생각하였다. 하지만 입력값이 정수가 아닌 문자열로 주어져 있기에, 흠칫했다. 그러고 나서 문제의 알고리즘 구분과 질문 글을 참고하니 자료 구조 중 해시 테이블과 관련된 내용이 적혀 있기에, 해시 테이블을 찾아보고 정리해보았다.

제대로 공부하는 것이 아니라, 이 문제를 찾기 위한 수준으로만 빠르게 정리해놓았기에, 해시 충돌(hash collision)이상의 내용은 정리하지는 않았다. 즉, map 자료구조를 통해 해시값을 지정하고 활용할 수 있도록 한다는 내용이다.

이를 기반으로, map 자료구조에서 find했을 때, 반환 이터레이터가 end()와 동일하다면, 존재하지 않는 다는 것이므로, 새로운 해시값을 할당하여 map에 삽입하도록, 이미 존재한다면, int형으로 저장해놓았던 해시값을 활용하는 방법으로 진행하였다.

이 외에는 일반적인 Union-Find 알고리즘과 동일한데, 난 여기서 굉장히 바보 같은 실수를 해서 20분 가량 헤매고 말았다.

문제에서 두 사람의 친구 관계의 네트워크에 몇 명이 있는지를 출력하라는 부분을 맨 첫줄을 기준으로 하는 줄 알고, 1번 친구의 친구 관계만 계속 출력하도록 해서 틀리고 있었다.

만약 이 문제를 풀 때, 44%에서 틀리고 있다면 아래의 테스트 케이스를 활용해보면 좋을 것 같다.

• TC1 (주의 : 여기서 input의 첫 줄은 1이여야 한다.)
• TC2

44%에서 틀리는 경우는, 이미 같은 부모 노드를 가지고 있는 애들을 합치면서 발생하는 문제이기에, 이를 조건문에서 별도 처리하는 과정을 거치면 쉽게 해결이 될 것이다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define MAX 100000 * 2

int t, f, value;
map<string, int> m;
int parent[MAX + 1];
int cnt[MAX + 1];
int findParent(int parent[], int x);
void unionParent(int parent[], int a, int b);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> t;
    while(t--) {
        memset(cnt, 0, sizeof(cnt));
        memset(parent, 0, sizeof(parent));
        m.clear();
        value = 1;

        cin >> f;

        for(int i = 0; i < f; i++) {
            int a, b;
            string A, B;
            cin >> A >> B;

            if(m.find(A) != m.end()) {
                a = m.find(A)->second;
            }
            else {
                a = value;
                parent[value] = value;
                m.insert({A, value});
                value++;
            }
            
            if(m.find(B) != m.end()) {
                b = m.find(B)->second;
            }
            else {
                b = value;
                parent[value] = value;
                m.insert({B, value});
                value++;
            }
            
            unionParent(parent, a, b);
        }
    }
    
    return 0;
}

int findParent(int parent[], int x) {
    if(parent[x] != x) {
        return parent[x] = findParent(parent, parent[x]);
    }

    return parent[x];
}

void unionParent(int parent[], int a, int b) {
    int pa = findParent(parent, a);
    int pb = findParent(parent, b);
    
    if(pa < pb) {
        parent[pb] = pa;
        cnt[pa] += cnt[pb] + 1;
        
        cout << cnt[pa] + 1 << endl;
    }
    else if(pa == pb) {
        cout << cnt[pa] + 1 << endl;    
    
        return ;
    }
    else {
        parent[pa] = pb;
        cnt[pb] += cnt[pa] + 1;

        cout << cnt[pb] + 1 << endl;
    }
}

• 문제 출처 : https://www.acmicpc.net/problem/4195
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.