[BOJ] 1043 - 거짓말(G4)

문제 링크

1043-거짓말

---

입력

첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.

둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.

셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.

N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수는 0 이상 50 이하의 정수, 각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수이다.

---

출력

첫째 줄에 문제의 정답을 출력한다.

---

문제 풀이

푸는게 어렵다기보다는 문제를 이해하는게 굉장히 헷갈리는 문제였다.

진실을 알고 있는 사람이 참석한 파티에 참석한 사람들은 모두 진실을 알게 된다.
즉, 진실을 아는 사람과 파티에 참가한 적 없는 사람끼리만 존재해야 거짓말을 할 수 있는 것!

우선 진실을 알고 있는 사람을 표시할 1차원 boolean 배열 know
파티에 함께 참석한 사람들을 표시할 2차원 boolean 배열 meet

진실을 알고 있는 사람 기준으로 bfs를 돌며 같은 파티에 참석한 사람들에게 진실을 알려준다.
결과적으로 같은 파티에 참여한 인원 모두 진실을 알거나, 모르는 경우 두가지 밖에 없다.
따라서 파티 인원 중 한 사람만 확인해도 전체 인원을 파악할 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static boolean[] know;
    static boolean[][] meet;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        know = new boolean[N + 1];
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        for (int i = 0; i < n; i++) {
            know[Integer.parseInt(st.nextToken())] = true;
        }

        int[][] party = new int[M][];
        meet = new boolean[N + 1][N + 1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int size = Integer.parseInt(st.nextToken());
 
            party[i] = new int[size];
            party[i][0] = Integer.parseInt(st.nextToken());

            for (int j = 1; j < size; j++) {
                party[i][j] = Integer.parseInt(st.nextToken());
                meet[party[i][j - 1]][party[i][j]] = meet[party[i][j]][party[i][j - 1]] = true;
            }

        }
        for (int i = 1; i <= N; i++) {
            if(know[i]) dfs(i);
        }

        int cnt = 0;
        for (int i = 0; i < M; i++) {
            if (!know[party[i][0]]) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }

    static void dfs(int n) {
        for (int i = 1; i <= N; i++) {
            if (meet[n][i] && !know[i]) {
                know[i] = true;
                dfs(i);
            }
        }
    }
}