[BOJ] 3098번. 소셜네트워크 (C++)

 

테스트케이스는 다 만족하는데 자꾸 틀렸습니다가 떠서 짬짬이 3일에 거쳐 맞혀낸 문제..

처음에 생각했던 방식으로 구현하고 싶은 고집 때문에 시간을 많이 날렸다. 여러분은 그러지 마세요..

 

이 문제를 해결하는 아이디어는

대칭 구조로 친구 관계를 저장하는 것이다.

 

예제와 함께 알아보자.

 

예제 1을 보면 첫 줄에 3(명) 2(가지 관계를 입력할 예정)이 나타나있다.

그 아래 1과 2가 친구, 2와 3이 친구인 상태라고 알려주고 있다.

 

이를 3x3배열에 다음과 같이 저장한다고 생각해보자.

	사람1	사람2	사람3
사람1	X(친구아님)	O(친구임)	X
사람2	O	X	O
사람3	X	O	X

 

1과 3이 친구면 3과 1도 당연히 친구인 것이니 위와 같이 대각선 대칭인 표를 그릴 수 있다.

 

이 원리를 사용해 다음과 같이 코드를 작성했다.

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<unordered_set<int>> social(N + 1);
    for (int i=0 ; i<M ; i++){
        int A, B;
        cin >> A >> B;
        social[A].insert(B);
        social[B].insert(A);
    }

    vector<int> day;
    int check = M*2;

    while (check < (N * (N - 1)) -1) {
        int tmp =0;
        vector<unordered_set<int>> m = social;
        for (int i = 1; i <= N; i++) {
            for (int z : social[i]) {
                for (int k : social[z]) {
                    if ((i != k) && (social[i].find(k) == social[i].end()) && (m[i].find(k)==m[i].end())){
                        m[i].insert(k);
                        tmp += 1;
                        check += 1;
                    }
                }
            }
        }
        for (int j=1 ; j<=N;j++)social[j].insert(m[j].begin(),m[j].end());
        day.push_back(tmp/2);
    }

    cout << day.size() << endl;
    for (int value : day) cout << value << endl;
    return 0;

}

social은 벡터다. 안에 unsigned_set을 담고 있다.

social 벡터의 [k]번째 요소는 k번째 사람의 친구 목록을 담고 있다.
친구 목록에는 우선순위가 필요없으므로 unsigned_set으로 정의했다. vector로 정의했을 때보다 탐색도 더 빠르다.

 

while 문 안에서는 m이라는 social의 복제 벡터를 사용하는데,
왜냐하면 social에서 새 친구 관계를 찾아내면서 동시에 새 친구를 업데이트 하면
무조건 하루만에 친구 관계가 전부 맺어지게 되므로 틀린 풀이가 되기 때문이다.
결국 하루 안에 일어난 친구 관계끼리는 서로 영향을 주면 안 되니

벡터 m에 하루 안에 생겨난 친구 관계를 담은 다음 m이 모두 모이면 그 m을 social에 업데이트했다.

 

아래 if문을 살펴보자.

while문은 i의 친구 z의 친구 k를 i의 친구로 추가하는 코드다. 이때 k가 i의 새친구로 추가되는 조건은, 1) k가 i 본인이 아니어야 하고, 2) 이미 친구가 아니어야하므로 social[i]에 k가 없어야하고, 3) 오늘 이미 다른 루트로 둘이 친구가 되지 않았어야 한다.

                    if ((i != k) && (social[i].find(k) == social[i].end()) && (m[i].find(k)==m[i].end())){
                        m[i].insert(k);
                        tmp += 1;
                        check += 1;
                    }

 

또 추가 테스트 케이스를 추천해보자면..

 

2 1

1 2 를 입력하면

 

0 이 출력되어야 하고

 

4 3

1 2

1 3

3 4 를 입력하면

 

2

2

1이 출력되어야 한다.