[백준] 1043 - 거짓말(Java)

문제 파악

지문

진실을 아는 자들이 진실을 퍼트린다고 생각하면 좋다.
진실이 다 퍼졌을 때에도 진실을 아는 이가 없는 파티가 있다면, 그 파티에서 지민이는 거짓말을 할 수 있다.

풀이

큐를 사용하여 풀었으며, 풀이 순서는 다음과 같다.

1. 입력으로 주어지는 진실을 아는 사람들을 큐에 넣어준다.
2. 큐에서 사람들을 꺼내며, 진실을 아는 사람임을 체크해 준다.
3. 진실을 아는 사람들이 참가한 파티를 역추적한다.
   • 진실을 아는 사람들이 참가한 파티는 지민이가 거짓말을 할 수 없으므로 답에서 제외한다.
4. 해당 파티에 참가한 참석자들을 큐에 다시 넣어준다.
   • 이 때, 이미 진실을 아는 사람은 큐에 추가할 필요가 없다. (단계 2에서 체크 했으므로)
   • 그렇게 되면 무한으로 사람들을 추가하게 될 것

코드

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

public class Main {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String[] input = br.readLine().split(" ");
            String[] truthLine = br.readLine().split(" ");

            int ppl = Integer.parseInt(input[0]);
            int partyCount = Integer.parseInt(input[1]);
            int truthCount = Integer.parseInt(truthLine[0]);

            boolean[] truthKnower = new boolean[ppl];
            // 진실을 아는 사람을 저장하는 큐
            LinkedList<Integer> truthQueue = new LinkedList<>();
            for (int i = 0; i < truthCount; i++) {
                int truthKnowerIdx = Integer.parseInt(truthLine[i + 1]) - 1;
                truthKnower[truthKnowerIdx] = true;
                truthQueue.offer(truthKnowerIdx);
            }

            boolean[] trueParty = new boolean[partyCount];
            boolean[][] participantMap = new boolean[ppl][partyCount];
            // 파티 참석 여부 저장
            // row - 사람, col - 파티
            for (int p = 0; p < partyCount; p++) {
                StringTokenizer tok = new StringTokenizer(br.readLine(), " ");
                int participantCount = Integer.parseInt(tok.nextToken());
                while (participantCount > 0) {
                    int participant = Integer.parseInt(tok.nextToken()) - 1;
                    participantMap[participant][p] = true;
                    participantCount--;
                }
            }

            while (!truthQueue.isEmpty()) {
                int truthPerson = truthQueue.poll();
                truthKnower[truthPerson] = true;
                for (int party = 0; party < partyCount; party++) {
                    if (!participantMap[truthPerson][party]) {
                        continue;
                    }
                    // 해당 파티에 진실을 아는 사람이 있다면 진실만을 말해야 하는 파티로 지정
                    trueParty[party] = true;
                    for(int participant = 0; participant < ppl; participant++) {
                        if (participantMap[participant][party] && !truthKnower[participant]) {
                            truthQueue.offer(participant);
                        }
                    }
                }
            }
            int answer = 0;
            for (boolean b : trueParty) {
                if (!b) {
                    answer++;
                }
            }
            System.out.println(answer);
        }
    }