[c++] BOJ 4195 :: 친구 네트워크

문제

친구 네트워크 문제 바로가기

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

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

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

 

풀이

특정 이름이 주어졌을 때 해당 이름이 속한 그룹을 알 수 있어야 하고, 해당 그룹에 있는 이름의 개수를 파악할 수 있어야 하는 문제이다.

이름이 속한 그룹을 바로 찾기 위해서는 map<string, int>를 이용할 수 있으며 해당 그룹에 있는 이름의 개수를 파악하기 위해서는 다음과 같은 방식으로 구현이 가능하다.

1. set<string> group[n]으로 특정 idx 그룹에 속하는 모든 이름은 저장해둘 수 있다.
2. 다른 set들의 관계로 표현할 수 있다.

예를 들어 다음과 같은 입력이 주어졌다고 하자.

1
5
a b // 그룹 1: a b
b c // 그룹 1: a b c
c a // 그룹 1: a b c
i j // 그룹 1: a b c, 그룹 2: i j
j a // 그룹 1: a b c i j

1번의 방식으로 하면 j a 입력이 들어왔을 때

• 기존의 그룹 1에 그룹 2의 요소를 모두 넣어 주어야 한다.
• 또한, 그룹 1로 합쳐졌다는 사실을 표현하기 위해 i와 j에 대해서는 map[i] = map[j] = 1;로 수정할 수 있지만 같은 그룹에 속하는 모든 요소에 대해서 map을 수정해주어야 한다.

첫번째 문제점은 어차피 그룹의 사이즈만을 묻는 문제의 특성을 이용하여 set이 아닌 int 형으로 바꿔서 숫자만 더해주는 식으로 개선할 수 있다.

두번째 문제점은 같은 그룹에 속하는 모든 요소에 대해 map을 수정하기보다 parent라는 배열을 하나 더 만들어서 그룹 간의 관계를 표현해줌으로써 해결할 수 있다. 위의 상황에서 parent[2] = 1;으로 표현하는 것이다.

결국 j a 입력이 들어왔을 때, j가 속한 그룹의 최상위 부모를 찾고(2) a가 속한 그룹의 최상위 부모(1)를 찾아서 두 그룹을 합친 뒤 나머지 한 그룹의 부모를 해당 그룹으로 할당해주면 된다.

처음 그룹을 생성될 때와 같이 고려해야하는 사항 더 있지만 코드로 살펴보자.

 

코드

#include <iostream>
#include <string>
#include <map>
#include <set>
#include <algorithm>

using namespace std;
map<string, int> friendMap; // 각 이름이 속한 그룹
int friendGroup[100001] = { 1, 0, }; // 해당 그룹의 요소 수
int parent[100001]; // 각 그룹의 부모
int groupSize = 1;

int findParent(int chlidGroup) { // find parent
    if (parent[chlidGroup] == chlidGroup) {
        // 최상위 부모이면
        return chlidGroup;
    }
    return findParent(parent[chlidGroup]);
}

int unionGroup(int group1, int group2) {
    int parentGroup = max(group1, group2);
    int childGroup = min(group1, group2);

    friendGroup[parentGroup] += friendGroup[childGroup];
    if (childGroup != 0) {
        parent[childGroup] = parentGroup;
    }

    return parentGroup;
}

int initGroup(int group) {
    friendGroup[group] = 2;
    parent[group] = group; // 처음엔 자기 자신이 부모
    return group;
}

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

    int T; cin >> T;
    while (T--) {
        friendMap.clear();

        int num; cin >> num;
        while (num--) { // 10^5
            string p1, p2;
            cin >> p1 >> p2;

            int p1Group = findParent(friendMap[p1]);
            int p2Group = findParent(friendMap[p2]);

            int group, anotherGroup;

            if (p1Group == p2Group) { // 같은 그룹에 속해있으면
                if (p1Group != 0) {
                    cout << friendGroup[p1Group] << '\n';
                    continue;
                }

                // 둘 다 처음이면
                group = initGroup(groupSize++);
            }
            else {
                // 다르면 합치기
                group = unionGroup(p1Group, p2Group);
            }

            friendMap[p1] = friendMap[p2] = group;
            cout << friendGroup[group] << '\n';
        }
    }
}

 

결과

문제	메모리	시간	코드 길이
4195	18520	244	1904