[백준 20501]https://www.acmicpc.net/problem/20501
문제 조건
"마, 내가 누군지 아나? 저커버그가 내 후임이다."
준원이는 저커버그와 함께 페이스북을 만들던 리즈시절을 회상하곤 한다... 저커버그가 페이스북을 다 만들기 직전, 바로 그 순간 저커버그에게 급똥이 찾아왔다. 그는 마지막 남은 기능 하나를 준원이에게 맡겼고, 그 기능이 바로 '함께 아는 친구' 기능이었다.
페이스북의 사용자는 총 N명이고, 각 사용자는 1번에서 N번까지로 번호 붙어 있었다. 준원이는, 사용자의 친구관계에 대한 정보가 모두 주어졌을 때,
"a번 사용자, b번 사용자와 공통적으로 친구 관계인 사용자의 수"
를 묻는 Q개의 질문에 차례로 답해야 했다.
준원이는 천하코일제딩대회 참가자 여러분에게 이 기능을 외주 맡겼다. 여러분이 이 기능을 대신 구현하면, 준원이는 여러분이 천하코일대딩제회에서 맞은 문제를 몰래 하나 늘여주겠다고 한다. 어떤가?
문제 입력
첫째 줄에, 사용자의 수를 나타내는 정수 N이 주어진다.
이후 N개의 줄에 걸쳐, 각 사람의 친구관계를 나타내는 길이 N의 문자열이 N개 주어진다. i번째 줄의 j번째 문자는, i번 사용자가 j번 사용자와 친구일 때에 1, 아닐 때에 0이다.
이후, 질문의 개수를 나타내는 정수 Q가 주어진다.
이후 Q개의 줄에 걸쳐, 질문을 나타내는 두 정수 a와 b가 공백을 사이에 두고 주어진다.
문제 풀기 전 설계
그래프를 묶는 건 분리 집합이라고 생각해서 사용하려니 분리 집합 문제가 아니라서 다른 방법을 고민해봤지만 풀리지 않았다.
문제 코드
package Baekjoon.bitmasking;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ_20501 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
int[][] friendRelationship = new int[2001][64]; // int = 2^32, 32 * 64 >= 2000 (2000비트 사용 가능)
for (int i = 1; i <= N; i++) {
String s = br.readLine();
for (int j = 1; j <= N; j++) {
char now = s.charAt(j - 1);
/**
* 친구 관계라면 친구 관계 배열에 비트로 저장
* 배열의 1칸 = int형 최대 크기 32비트까지 저장 가능
* friendRelationship[본인 번호][상대 번호를 기준값(32)으로 나눈 몫] = 상대방과 친구 관계를 true로 변경
* 배열 1칸에 32명씩 친구 관계가 저장되어 있다고 보면 된다.
* |= 연산은 기존 값과 우측 값을 비트 OR 연산한 결과를 대입한다는 의미
*/
if (now == '1') friendRelationship[i][j / 32] |= (1 << (j % 32));
}
}
int Q = Integer.parseInt(br.readLine());
while (Q-- > 0) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
long sum = 0;
for (int i = 0; i < 64; i++) {
/**
* 0 ~ 2048(32 * 64)의 범위를 탐색하여 a와 b에 해당하는 배열 값을 비트 AND 연산하면
* 같은 자리에 1이 있는 경우만 남는다. 즉 공통된 친구만 남길 수 있다.
* Integer.bitCount = int형 정수를 이진수로 변환했을 때 1의 개수를 구하는 메소드
*/
sum += Integer.bitCount(friendRelationship[a][i] & friendRelationship[b][i]);
}
sb.append(sum).append('\n');
}
System.out.println(sb);
}
}문제 풀이
결국 검색을 통해 푸는 방법을 알게 되었다. 허무하게도 비트마스킹을 응용하면 풀 수 있는 문제이다. 보통 비트마스킹은 N이 정수형(32 or 64bit) 크기를 초과하면 사용하지 못한다고 생각하는데, 정수형 배열을 통해 이를 해결할 수 있다.
arr[입력값 / 정수형 크기] = 입력값 % 정수형 크기
위의 형태로 입력값을 쪼개서 저장한다면 큰 값도 비트를 이용한 상태를 저장할 수 있다.
지금 문제는 나와 친구인지를 체크하려면 최대 2000bit가 필요하기 때문에 배열의 크기를 int형 배열 arr[N + 1][64]로 잡아서 배열 한 칸에 32명(2^0 ~ 2^31)의 상태를 저장할 수 있게 했다. (64 * 32 = 2048이므로 N명을 모두 담을 수 있는 크기이다.)
이렇게 친구 관계를 저장하고 나면 Q개의 쿼리에서 사용자 a, b를 입력받아 그 인덱스에서 반복문을 통해 각 위치에서 bit AND 연산을 하여 나온 정수는 공통된 친구를 의미한다. 그 정수를 이진수로 변환해 1의 개수를 센다면 그것이 공통 친구의 수가 된다.
Review
비트마스킹은 N이 크면 사용하지 못하는 줄로만 알았는데 이번 문제를 풀면서 지식이 확장되었다. 알고나면 간단하지만 쉽게 생각하지 못했던 내 사고 유연성이 조금이나마 길러졌으면 좋겠다.
