백준 1043 거짓말

코드 1

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

public class Lie {
    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());
        st = new StringTokenizer(br.readLine());
        int knowNum = Integer.parseInt(st.nextToken());
        HashSet<Integer> knows = new HashSet<>();
        for (int i = 0; i < knowNum; i++) {
            int num = Integer.parseInt(st.nextToken());
            knows.add(num);
        }
        int[][] party = new int[M][50];
        boolean[] check = new boolean[M];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int partyNum = Integer.parseInt(st.nextToken());
            for (int j = 0; j < partyNum; j++) {
                party[i][j] = Integer.parseInt(st.nextToken());
                if(knows.contains(party[i][j])){ //진실을 아는사람이 있는 파티에 check표시
                    check[i] = true;
                }
            }
            if(check[i]){ // 해당 파티를 다시 돌며, 파티 인원 전부 knows에 추가
                for (int j = 0; j < partyNum; j++) {
                    knows.add(party[i][j]);
                }
            }
        }

        while (true){// 진실을 아는사람 탐색
            boolean flag = false;// 진실을 새로 알게된 사람이 있다면 flag = true

            for (int i = 0; i < M; i++) {
                for (int j = 0; j < 50; j++) {
                    if(!check[i]&&knows.contains(party[i][j])){ // 진실을 모르는 파티중, 진실을 아는자가 그파티에 있다면,
                        check[i] = true;
                        flag = true; // 해당 파티에 진실을 새로 알게된 사람이 있음
                        break;
                    }
                }
                if(check[i]){// 진실을 아는 파티에 인원 knows 에 추가
                    for (int j = 0; j < 50; j++) {
                        if(party[i][j]==0) break;
                        knows.add(party[i][j]);
                    }
                }
            }
            if(!flag) break;// 새로 진실을 알게된 사람이 없다면 탈출
        }

        int count = 0;
        for (int i = 0; i < M; i++) {// 진실을 모르는 파티 count
            if(!check[i]){
                count++;
            }

        }
        System.out.println(count);
    }
}

풀이방법

1. 진실을 아는 사람들을 knows hashset에 넣고, 진실을 아는사람이 있는 파티 check배열에 표시한다.
2. 진실을 아는사람과 같은 파티 사람들을 전부 knows hashset에 넣는다.
3. 다시 파티를 탐색하며, 1,2번을 반복한다.
4. 더이상 진실을 알수 있는사람이 없을때, 반복을 빠져나온다.
5. 파티를 다시 탐색하며, check 표시가 안되어있는 파티를 찾는다.

코드 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Lie2 {
    static int[][] map;
    static boolean[] visit;
    static int[][] party;
    static int N;
    static int M;
    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());
        party = new int[M][N];
        map = new int[N+1][N+1];
        visit = new boolean[N+1];
        ArrayList<Integer> knows = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        int knowNum = Integer.parseInt(st.nextToken());
        for (int i = 0; i < knowNum; i++) {
            int perNum = Integer.parseInt(st.nextToken());
            knows.add(perNum);
            visit[perNum] = true;
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int partyPer = Integer.parseInt(st.nextToken());
            for (int j = 0; j < partyPer; j++) {
                party[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 0; i <M; i++) { // 같은 party 사람들끼리 연결
            for (int j = 0; j < party[i].length; j++) {
                for (int k = j; k < party[i].length; k++) {
                    map[party[i][j]][party[i][k]] = map[party[i][k]][party[i][j]] = 1;
                }
            }
        }
        for (int know: knows) {
            bfs(know);
        }
        int count = 0;
        for (int i = 0; i < M; i++) {
            boolean flag = false;
            for (int j = 0; j < party[i].length; j++) {
                if(visit[party[i][j]]){
                    flag = true;
                }
            }
            if(!flag) count++;
        }
        System.out.println(count);
    }
    public static void bfs(int know){
        Queue<Integer> que = new LinkedList<>();
        que.add(know);
        while (!que.isEmpty()){
            int known = que.poll();
            for (int i = 1; i <= N; i++) {
                if(!visit[i]&& map[known][i]==1){
                    visit[i] = true;
                    que.add(i);
                }
            }
        }
    }
}

풀이방법

1. 입력값을 받고 같은 파티의 사람들끼리 연결한다.
2. 📢 [1,2,3] 가 있을때, (1,2),(1,3),(2,3) 이런식으로 탐색한다.
   이때, 2차원 map에 (1,2)(2,1) , (1,3)(3,1), (2,3)(3,2) 좌표에 1을 대입해서 연결되었음을 표시한다.
3. 기존에 주어진 진실을 아는사람을 파라미터로하는 bfs 탐색을 시작한다.
4. 진실을 모르는사람인데, 진실을 아는사람과 map상에서 연결되었다면, visited[i] = true 체크해준다. 즉, 진실을 아는사람이 된다.
   이 사람을 다시 큐에넣고 해당 로직을 반복한다.
5. bfs탐색이 끝나면, 진실을 전해들은 사람 포함해서, 진실을 아는사람을 모두 구해놓은 상태이다.
   이후 파티를 다시 돌면서, 진실을 아는사람이 없는 파티의 갯수를 센다.

후기

bfs로 탐색하는 풀이가 정석인 풀이다.
파티 인원들끼리 연결시키는 부분을 map[i][j] = map[j][i] = 1 로직을 썼는데, 이 로직이 핵심인것 같다.