백준 20501 - Facebook (C++)

문제

• 문제 링크

  
   BOJ 20501 - Facebook 
  

• 문제 요약

$N$명의 친구 관계 정보가 주어진다.
$Q$개의 쿼리에 대해 그에 맞는 답을 출력하자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$2 ≤ N ≤ 2,000$

$1 ≤ Q ≤ 500,000$

알고리즘 분류

• 비트 집합(bit set)
• 비트마스킹(bitmask)

풀이

$B[2000][2000]$의 배열에 담아 쿼리 당 $N$번의 연산을 수행하면 $O(NQ)$로 시간 초과를 피할 수 없다.

친구 관계를 이진수로 간단히 표현할 수 있으므로 $B[2000][⌈2000 / 64⌉]$를 가지고 mask로 처리하면 $O(NQ / 64)$ 의 복잡도로 해결할 수 있다.

아래 코드는 직접 mask로 구현한 것과 C++ STL의 bitset 을 이용한 코드이다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
long long n, q, i(1), j, B[2001][33];
 
int main()
{
    for (cin >> n; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (scanf("%1d", &q); q) B[i][j / 64] |= 1LL << (j % 64);
    for (cin >> q; q--; printf("%d\n", n))
    {
        scanf("%d %d", &i, &j); n = 0;
        for (int k{}; k < 33; k++)
            n += __builtin_popcountll(B[i][k] & B[j][k]);
    }
}
 
-------------------------------------------------------------------------------
 
#include<bits/stdc++.h>
using namespace std;
 
bitset <2000> B[2000];
int n, q, i, j;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (cin >> n; i < n; i++)
    {
        string s; cin >> s;
        B[i] = bitset <2000>(s);
    }
    for (cin >> q; q--;)
        cin >> i >> j, cout << (B[--i] & B[--j]).count() << '\n';
}

comment

끝