[백준] 1043 거짓말 - JAVA

1043번: 거짓말 (acmicpc.net)

1043번: 거짓말

long 자료형 비트 연산 때문에 고생한 문제....

기본적인 CS 지식이 부족하다고 느꼈다.

 

풀이

알고리즘 파악

비트 마스킹, 유니온 파인드

 

문제를 정리하면, 결국 지민이는 둘 중 하나를 선택해야 한다. 

과장하기 vs 진실을 말하기

그런데 여기서 조건이 있다. 과장을 한 대상에게 진실을 말하면 안 되고, 진실을 말한 대상에게 과장을 하면 안 된다는 것이다. 즉, 바이러스에 감염되듯이 진실을 들을 대상과 같이 파티에 참석한 인원은 전부 진실을 알게 되는 것이며, 결국 진실병(?)에 감염되지 못한 그룹만 찾으면 된다.

 

구현

 

이를 비트 마스킹으로 구현하였다. 인원의 최대 수가 50이기 때문에 64bit의 저장공간을 가지고 있는 long 자료형으로 집합의 표현이 가능했다. 진실을 들은 인원들은 mambers로 정의하였고, while문 속 for문으로 각 파티를 돌며 진실병이 감염된 인원이 있는지를 &비트 연산으로 확인하고 , 멤버가 있으면  |연산으로 그룹의 멤버를 전부 합하였다(진실병 전염).

진실병에 감염된 파티수를 하나씩 줄여 더 이상 줄지 않을 시 반복문을 나왔다. 또한 visit 배열을 통해 중복 count을 방지하였다. 

 

여기까지는 순조로왔으나...

 

난관

 

문제는 바로 long 자료형의 비트 연산이였다... long의 비트 연산은 한쪽이 long 타입이 아니면 계산이 int로 연산되는 것이었다. 아주 기초적인 부분인데 이를 몰랐고 1~2시간을 헤맸다. 역시 기초가 튼튼해야 된다!

 

ex) long|= (1<<50)  -> X (int로 계산됨)     long|= ((long)1<<50) -> O

 

 

 

 

 

 

import java.io.*;
import java.util.StringTokenizer;
public class Main {
	public static void main(String[] args) throws IOException{
		
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
    long[] parties = new long[m];
    boolean[] visit = new boolean[m];

    st = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st.nextToken());
    long members=0;

    for(int i=0; i<a; i++) members |= ((long)1<<Integer.parseInt(st.nextToken())); //진실을 아는 사람

    for(int i=0; i<m; i++) {
        st = new StringTokenizer(br.readLine());
        int temp = Integer.parseInt(st.nextToken());
        for(int j=0; j<temp; j++) parties[i] |= ((long)1<<Integer.parseInt(st.nextToken()));//파티들
    }

    boolean end=false;
    int answer = m;
    while(!end) {
        end =true;
        for(int i=0; i<m; i++)
        {
            if(!visit[i] && ((members & parties[i]) >0)) //교집함
            {
                visit[i] = true;
                members |=parties[i]; //합집합
                end = false;
                answer--;
            }
        }
    }

    bw.write(Integer.toString(answer));
    bw.flush();
    bw.close();
    br.close();
	}   
}