백준 1043번: 거짓말(java)

 

💡 문제 요약

• 진실을 아는 사람들이 일부 있고, M개의 파티가 열림
• 파티에 참여한 사람 중 진실을 아는 사람이 있다면, 해당 파티에서 거짓말을 할 수 없음
• 한 번 진실을 알게 되면 연결된 파티, 사람을 통해 전파됨 (BFS 활용)
• 거짓말을 할 수 있는 파티의 수를 구하는 문제

---

📅 조건 요약

• 사람 수 N (1 ≤ N ≤ 50)
• 파티 수 M (1 ≤ M ≤ 50)
• 진실을 아는 사람 수 K (0 ≤ K ≤ N)
• 각 파티에 참석한 사람들의 목록 주어짐

---

🔍 입력 형식

N M
K 진실을 아는 사람 번호들...
파티1 참석 인원 수 번호 번호 ...
파티2 참석 인원 수 번호 번호 ...
...

---

✅ 출력 형식

• 거짓말을 할 수 있는 파티의 수 출력

---

🧠 알고리즘 설계

1. 진실을 아는 사람들을 큐에 저장 (BFS 시작점)
2. 각 사람이 어떤 파티에 참석했는지 기록
3. BFS로 진실 전파:
   • 진실을 아는 사람이 참석한 파티라면 해당 파티의 다른 참석자도 진실을 알게 됨
   • 전파된 사람들도 다시 큐에 넣어 탐색 반복
4. BFS 종료 후, 진실이 전파되지 않은 파티 수 세기

---

🔑 핵심 구현 코드

Queue<Integer> queue = new ArrayDeque<>();
for (진실을 아는 사람 p)
    trueList[p] = 1; queue.offer(p);

while (!queue.isEmpty()) {
    int person = queue.poll();
    for (int partyIdx : peopleAttendedParty.get(person)) {
        if (partyVisited[partyIdx]) continue;
        partyVisited[partyIdx] = true;
        for (int p : parties.get(partyIdx)) {
            if (trueList[p] == 0) {
                trueList[p] = 1;
                queue.offer(p);
            }
        }
    }
}

---

🗂 전체 코드

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

public class Main {

    public static Integer convertInt(String word) {
        return Integer.parseInt(word);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = convertInt(st.nextToken());
        int M = convertInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int trueNum = convertInt(st.nextToken());
        int[] trueList = new int[N + 1];
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < trueNum; i++) {
            int p = convertInt(st.nextToken());
            trueList[p] = 1;
            queue.offer(p);
        }

        List<List<Integer>> parties = new ArrayList<>();
        List<List<Integer>> peopleAttendedParty = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            peopleAttendedParty.add(new ArrayList<>());
        }
        for (int i = 0; i < M; i++) {
            parties.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int partyNum = convertInt(st.nextToken());
            for (int j = 0; j < partyNum; j++) {
                int p = convertInt(st.nextToken());
                parties.get(i).add(p);
                peopleAttendedParty.get(p).add(i);
            }
        }

        boolean[] partyVisited = new boolean[M];
        while (!queue.isEmpty()) {
            int person = queue.poll();
            for (int partyIdx : peopleAttendedParty.get(person)) {
                if (partyVisited[partyIdx]) continue;
                partyVisited[partyIdx] = true;
                for (int p : parties.get(partyIdx)) {
                    if (trueList[p] == 0) {
                        trueList[p] = 1;
                        queue.offer(p);
                    }
                }
            }
        }

        int count = 0;
        for (int i = 0; i < M; i++) {
            if (!partyVisited[i]) {
                count++;
            }
        }

        System.out.println(count);
    }
}

---

⏱️ 시간 복잡도

단계 시간

입력 처리	O(N + M)
BFS 탐색	O(N + M)
출력 계산	O(M)

⮕️ 전체적으로 O(N + M) 수준의 시간 복잡도