[C/C++] 백준 - 20501번 : Facebook (비트집합)

https://www.acmicpc.net/problem/20501

20501번: Facebook

문제

"마, 내가 누군지 아나? 저커버그가 내 후임이다."

준원이는 저커버그와 함께 페이스북을 만들던 리즈시절을 회상하곤 한다... 저커버그가 페이스북을 다 만들기 직전, 바로 그 순간 저커버그에게 급똥이 찾아왔다. 그는 마지막 남은 기능 하나를 준원이에게 맡겼고, 그 기능이 바로 '함께 아는 친구' 기능이었다.

페이스북의 사용자는 총 N명이고, 각 사용자는 1번에서 N번까지로 번호 붙어 있었다. 준원이는, 사용자의 친구관계에 대한 정보가 모두 주어졌을 때,

"a번 사용자, b번 사용자와 공통적으로 친구 관계인 사용자의 수"

를 묻는 Q개의 질문에 차례로 답해야 했다.

준원이는 천하코일제딩대회 참가자 여러분에게 이 기능을 외주 맡겼다. 여러분이 이 기능을 대신 구현하면, 준원이는 여러분이 천하코일대딩제회에서 맞은 문제를 몰래 하나 늘여주겠다고 한다. 어떤가?

입력

첫째 줄에, 사용자의 수를 나타내는 정수 N이 주어진다.

이후 N개의 줄에 걸쳐, 각 사람의 친구관계를 나타내는 길이 N의 문자열이 N개 주어진다. i번째 줄의 j번째 문자는, i번 사용자가 j번 사용자와 친구일 때에 1, 아닐 때에 0이다.

이후, 질문의 개수를 나타내는 정수 Q가 주어진다.

이후 Q개의 줄에 걸쳐, 질문을 나타내는 두 정수 a와 b가 공백을 사이에 두고 주어진다.

출력

Q개의 줄에 걸쳐, 각 질문에 대한 답을 나타내는 정수를 하나씩 차례대로 출력한다.

---

boolean 배열을 통해 a, b 동시에 이웃한 정점의 개수를 구하는 풀이가 가장 간단한 풀이가 되겠지만 N의 최대 크기가 2,000 / Q의 최대크기가 500,000일 경우 시간 내 통과가 불가능하다. 이를 최적화하는 방법은 비트집합을 이용한 방법이다.

 

N이 32 이하라면 한 사람의 친구 관계를 int형(32비트 정수) 변수 하나로 표현할 수 있다. 이 때 a,b와 동시에 이웃한 정점은 두 정수에 and 연산을 취한 값에서 켜진 비트의 개수가 된다.

 

그러므로 친구 관계를 N/32개의 int형 변수로 관리해주면 연산량을 32배 줄일 수 있다. long long형(64비트 정수)을 사용하면 64배 줄일 수 있다. 

 

이와 같은 테크닉을 bitset라고 부른다. 따라서, 시간 복잡도는 O(NQ/64)가 된다.

 

C/C++에서 gcc 컴파일러를 사용하는 경우, 정수 자료형에서 켜진 비트의 개수를 빠르게 구해주는 함수가 있다. 이 함수를 이용하면 편하게 알아낼 수 있다. 

 

• int형은 __builtin_popcount
• long long형은 __builtin_popcountll

을 사용하면 된다.

 

#include <bits/stdc++.h>
#define endl '\n'

int N;
long long s[2020 + 1][34 + 1];

void input(){
	scanf("%d", &N);
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			int rel; 
			scanf("%1d", &rel);
			if(rel) s[i][j/60] |= 1LL << (j % 60);
		}
	}
}

void solution(){
	int Q;
	scanf("%d", &Q);
	while(Q--){
		int a, b, cnt = 0;
		scanf("%d %d", &a, &b);
		for(int i=0;i<35;i++){
			cnt += __builtin_popcountll(s[a][i] & s[b][i]);
		}
		printf("%d\n", cnt);
	}
}
 
int main() {
	input();
	solution();
 
	return 0;
}