[백준] 1043 거짓말

1. 문제

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

1043번: 거짓말

2. 접근방법

진실된 사람은 전염이 된다.

진실인 사람과 같이 파티하는 사람과 같이 파티하는 사람에게도 거짓을 말해선 안된다.

 

그러므로 bfs나 dfs를 이용해 진실된 사람과 연관된 사람을 모두 체크해준뒤

파티 중 이런 사람들이 없는 파티의 갯수를 구하면 된다.

 

set을 이용해 나와 한번이라도 파티를 한 사람들을 각각 저장해 그래프 형태로 저장을 하고

dfs를 이용해서 그래프 탐색을 하면 된다.

여기서 visit 체크도 set을 이용해서 하면 쉽게 풀이 가능하다.

 

 

3. 자바 코드

package backjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class P1043거짓말 {

    static Set<Integer> trueFriends = new HashSet<>();
    static Set<Integer>[] manMap;
    public static void main(String[] args) throws Exception {
        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());//파티
        manMap = new HashSet[N+1];
        for(int i = 0 ; i < N+1 ; i++) manMap[i] = new HashSet<>();
        st = new StringTokenizer(br.readLine());
        int trueMan = Integer.parseInt(st.nextToken());
        int [] trueMans = new int[trueMan];
        ArrayList<int[]> parties = new ArrayList<>();
        for(int i = 0 ; i < trueMan ; i++) trueMans[i] = Integer.parseInt(st.nextToken());
        for(int i = 0 ; i < M ; i++){
            st = new StringTokenizer(br.readLine());
            int man = Integer.parseInt(st.nextToken());
            int [] mans = new int [man];
            for(int j = 0 ; j < man ; j++) mans[j] = Integer.parseInt(st.nextToken());
            for(int j = 0 ; j < man ; j++){
                for(int k = 0 ; k < man ;k++){
                    if(j==k)continue;
                    manMap[mans[j]].add(mans[k]);
                }
            }
            parties.add(mans);
        }
        for(int i = 0 ; i < trueMans.length ; i++){
            if(trueFriends.add(trueMans[i])){
                dfs(trueMans[i]);
            }
        }
        int answer = 0;
        for(int party [] : parties){
            boolean flag = true;
            for(int man : party){
                if(trueFriends.contains(man)){
                    flag =false;
                    break;
                }
            }
            if(flag) answer++;
        }
        System.out.println(answer);
    }
    static void dfs(int num){
        for(int n : manMap[num]){
            if(trueFriends.add(n)){
                dfs(n);
            }
        }
    }
}

4. 마치며