[백준] 1043번: 거짓말 - JAVA

🔗 문제 링크

BOJ 1043번: 거짓말

1043번: 거짓말

 

📝 풀이 과정

진실을 아는 사람이 한 사람이라도 파티에 있게 되면 해당 파티의 사람들은 모두 진실을 알게 된다. 따라서, 진실을 아는 사람과 파티에 참가한적 없는 사람끼리만 존재해야 거짓말을 할 수 있는 파티이다.

 

같은 파티에 참가한 사람들끼리 연결을 해준 뒤, 진신을 알게된 사람을 기준으로 DFS를 돌며 같은 파티에 참가한 사람들에게 모두 진실을 알려준다. 같은 파티에 참가한 사람들을 모두 진실을 알거나, 모르는 경우이기 때문에 파티에 참가한 사람들 중 1사람만 조사해 보아도 된다.

 

💻 코드

import java.util.Scanner;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        know = new boolean[N + 1];
        int len = sc.nextInt();
        for (int i = 0; i < len; i++)
            know[sc.nextInt()] = true;

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

        for (int i = 0; i < M; i++) {
            int input = sc.nextInt();
            party[i] = new int[input];

            party[i][0] = sc.nextInt();

            for (int j = 1; j < input; j++) {
                party[i][j] = sc.nextInt();
                adj[party[i][j - 1]][party[i][j]] = adj[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 (adj[n][i] && !know[i]) {
                know[i] = true;
                dfs(i);
            }
        }
    }
}

 

📊 제출 결과