[백준] 1043번: 거짓말 (Java)

문제

링크 : https://www.acmicpc.net/problem/1043

난이도 : 골드4

알고리즘 : 그래프 탐색

---

풀이 과정

문제에서 지민이는 거짓말하기를 좋아한다. 거짓말쟁이라는 것을 들키지 않으면서 최대한 많은 파티에서 거짓말을 하려한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 진실을 아는 사람에게 거짓말을 하거나, 거짓을 아는 사람에게 진실을 말하면 거짓말쟁이라는 것을 들키게 된다.  따라서 진실을 아는 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 이 때, 거짓말을 할 수 있는 파티 개수의 최댓값을 구해야 한다.

 

풀이의 핵심은 '진실을 아는 사람들과 같은 파티에 참가한 사람은 모두 진실을 아는 사람이다.' 라는 것이다. 

진실을 아는 사람이 있는 파티는 반드시 진실을 이야기해야 하고, 그 파티의 모든 사람들은 이제부터 진실을 아는 사람이 된다. 이 사람들이 다른 파티에 참가하는 경우 그 파티에서도 지민이는 진실을 이야기해야 한다.

결국 지민이는 진실을 아는 사람들과 한 번도 만나지 않는 사람들이 모인 파티에서만 거짓말을 할 수 있는 것이다. 

이 때, 결국에는 진실을 알게 되는 사람을 어떻게 알 수 있을까? 

BFS를 사용하면 알 수 있다. 먼저, 사람들 간의 같은 파티 소속 여부를 저장해야 한다. 각각의 사람을 노드로 생각하고 같은 파티에 속한 경우 연결된 노드로 생각하여 BFS를 수행하면 결국에 진실을 알게되는 모든 사람을 알 수 있는 것이다. 

 

진실을 알게 되는 모든 사람을 찾고 나서, 이 사람들이 한 명도 속하지 않은 파티의 수는 거짓말을 할 수 있는 파티의 수와 같다.

---

코드

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        boolean[] knowTruth = new boolean[n+1];
        boolean[][] meet = new boolean[n+1][n+1];

        st = new StringTokenizer(br.readLine());
        int knowTruthNum = Integer.parseInt(st.nextToken());
        for(int i=0;i<knowTruthNum;i++){
            knowTruth[Integer.parseInt(st.nextToken())] = true;
        }

        List<Integer>[] parties = new List[m];
        for(int i=0;i<m;i++){
            parties[i] = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            int memberNum = Integer.parseInt(st.nextToken());
            for (int j = 0; j < memberNum; j++) {
                int member = Integer.parseInt(st.nextToken());
                for (int k = 0; k < parties[i].size(); k++) {
                    meet[member][parties[i].get(k)] = true;
                    meet[parties[i].get(k)][member] = true;
                }
                parties[i].add(member);
            }
        }

        bfs(meet, knowTruth);

        int answer = 0;
        for(int i=0;i<m;i++){
            boolean canLie = true;
            for(int member : parties[i]){
                if(knowTruth[member]){
                    canLie = false;
                }
            }
            if(canLie) answer++;
        }

        System.out.print(answer);
    }

    static void bfs(boolean[][] meet, boolean[] knowTruth){
        Queue<Integer> q = new LinkedList<>();
        boolean[] isVisited = new boolean[knowTruth.length];
        for(int i=0;i<knowTruth.length;i++){
            if(knowTruth[i]) q.add(i);
        }

        while(!q.isEmpty()){
            int now = q.poll();
            isVisited[now] = true;
            for(int i=0;i<meet[now].length;i++){
                if(!meet[now][i] || isVisited[i]) continue;
                q.add(i);
                knowTruth[i] = true;
            }
        }
    }
}