[백준] 1043번: 거짓말 (java)

1043번: 거짓말 (acmicpc.net)

1043번: 거짓말

어떻게 생각하고 문제를 풀었는가?

진실을 아는 사람과 같은 파티에 속한 사람은 진실을 아는 사람이 됩니다.

결과적으로 과장된 이야기를 할 수 있는 파티를 찾기 위해서는 진실을 아는 사람들과 같은 파티에 참여하지 않아야 합니다.

BFS로 진실을 아는 사람들이 참여하는 파티를 순회하며 다른 사람들을 queue에 넣음으로써 진실을 아는 파티와 그렇지 않은 파티를 계산할 수 있을 것이라고 생각하였습니다.

코드

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer;
        tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken());
        List<Integer>[] participating = new List[N+1];
        for(int i=1; i<=N; i++){
            participating[i] = new ArrayList<>();
        }
        int M = Integer.parseInt(tokenizer.nextToken());
        tokenizer = new StringTokenizer(reader.readLine());
        int truth = Integer.parseInt(tokenizer.nextToken());
        boolean[] enlightened = new boolean[N+1];
        Queue<Integer> queue = new LinkedList<>();
        for(int i=0; i<truth; i++){
            queue.add(Integer.parseInt(tokenizer.nextToken()));
        }
        int[][] attendees = new int[M][];
        for(int i=0; i<M; i++){
            tokenizer = new StringTokenizer(reader.readLine());
            int quota = Integer.parseInt(tokenizer.nextToken());
            attendees[i] = new int[quota];
            for(int j=0; j<quota; j++){
                int person = Integer.parseInt(tokenizer.nextToken());
                attendees[i][j] = person;
                participating[person].add(i);
            }
        }
        reader.close();
        
        boolean[] parties = new boolean[M];
        while(!queue.isEmpty()){
            int person = queue.poll();
            if(enlightened[person]) continue;
            enlightened[person] = true;
            for(int party : participating[person]){
                if(parties[party]) continue;
                for(int other : attendees[party]){
                    queue.add(other);
                }
                parties[party] = true;
            }
        }

        int result = 0;
        for(boolean exaggerated : parties){
            if(!exaggerated) {
                result++;
            }
        }
        System.out.println(result);
    }
}

Queue를 사용하여 BFS를 구현하였습니다.

이번 문제에서는 파티에 속한 사람들의 정보들이 주어지고, 진실을 아는 사람들을 순회하여 다른 사람들을 queue에 추가해야 하기 때문에 각 사람들이 참여하는 파티들의 정보를 List 배열로, 각 파티에 참여하는 사람들의 정보를 2차원 int 배열로 선언하였습니다.

Queue를 순회하며 해당 사람이 참여한 파티들 중 체크하지 않은 파티에 대해 진실을 몰랐던 사람들을 Queue에 넣음으로써 결과적으로 진실을 아는 파티와 모르는 파티를 가려낼 수 있습니다.