1043번. 거짓말

 

 

아이디어

이 문제의 핵심은 크게 2가지이다.

1) 진실을 알고 있는 사람은 함께 파티에 참여한 사람에게 진실을 전파한다

2) 거짓말과 진실을 번갈아 듣는 사람이 있어서는 안된다

 

따라서 초기에 진실을 알고 있는 사람이 함께 파티에 참여한 사람에게 진실을 전파하고, 이 사람들이 또 파티에 함께 참여한 사람들에게 진실을 전파하는 구조인 것이다.

 

따라서 함께 파티에 참여한 사람들을 그래프 형태로 만들고 dfs 를 활용해 진실을 전파하면 '진실을 들어야 하는 사람들' 을 알 수 있게 된다.

 

이후 파티 참가자들을 확인하면서 '진실을 들어야 하는 사람'이 포함된 파티는 진실을 말하고 그렇지 않은 파티는 거짓말을 하면 된다

 

 

풀이코드

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

public class _n1043_ {
    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];

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

        boolean[][] meet = new boolean[N + 1][N + 1];
        List<int[]> parties = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int numOfAppender = Integer.parseInt(st.nextToken());
            // 참가자들 번호(이걸 통해서 그래프 만들자)
            int[] appender = new int[numOfAppender];
            for (int j = 0; j < numOfAppender; j++) {
                appender[j] = Integer.parseInt(st.nextToken());
            }
            parties.add(appender);

            for (int x = 0; x < numOfAppender - 1; x++) {
                for (int y = x + 1; y < numOfAppender; y++) {
                    int p1 = appender[x];
                    int p2 = appender[y];

                    meet[p1][p2] = meet[p2][p1] = true;
                }
            }
        }

        for (int i = 0; i < N + 1; i++) {
            if (knowTruth[i]) {
                // dfs 수행
                dfs(knowTruth, meet, i);
            }
        }

        int result = 0;
        for (int[] appenders : parties) {
            boolean canLie = true;
            for (int appender : appenders) {
                if (knowTruth[appender]){
                    canLie = false;
                    break;
                }
            }

            if (canLie) result++;
        }

        System.out.println(result);
    }

    public static void dfs(boolean[] knowTruth, boolean[][] meet, int person) {
        boolean[] together = meet[person];

        for (int i = 0; i < together.length; i++) {
            if (together[i] && !knowTruth[i]) {
                knowTruth[i] = true;
                dfs(knowTruth, meet, i);
            }
        }
    }
}