<java> 백준 1043 - BFS, 그래프

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

 

1. 처음 생각한 간단한 방식

• 진실을 아는 사람이 파티에 참석하면 모두 진실만 말함
• 진실을 아는 사람이 온 파티의 모든 참석자는 이후 항상 진실만 말함
• 전체 파티를 탐색하여 진실을 아는 사람 존재 여부 확인
• 있으면 해당 파티를 "진실을 아는 파티"로 추가

→ 순서대로 하게 되면 여러 반례들이 생김 

 

2. 그래프 기반 접근법

• 파티 참석자들 간의 그래프 생성
• 진실을 아는 사람과 연결된 모든 사람도 진실을 알게 됨
• BFS로 진실을 아는 사람 표시
• 마지막으로 재확인하며 진실을 모르는 사람만 참석한 파티 수 계산 (answer 증가)

 

아마 유니온 파인드를 원하는 문제 같기는 한데 정확하게 기억이 안나서 추후 유니온 파인드에 대해
정리해 보아야겠다.

 

정답

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class Q1043A {
    static int answer, n, m, knowPersonNum;
    static boolean[] knowPerson;
    static List<List<Integer>> g = new ArrayList<>();
    static List<List<Integer>> parties = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] str = reader.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        knowPerson = new boolean[n + 1];

        str = reader.readLine().split(" ");
        knowPersonNum = Integer.parseInt(str[0]);
        for (int i = 0; i < knowPersonNum; i++) {
            knowPerson[Integer.parseInt(str[i + 1])] = true;
        }


        for (int i = 0; i <= n; i++) {
            g.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            str = reader.readLine().split(" ");
            int partyNum = Integer.parseInt(str[0]);
            int[] temp = new int[partyNum];
            parties.add(new ArrayList<>());
            for (int j = 0; j < partyNum; j++) {
                temp[j] = Integer.parseInt(str[j + 1]);
                parties.get(i).add(temp[j]);
            }
            for (int j = 0; j < partyNum; j++) {
              //각 파티에 온 사람들 끼리 그래프 생성
                for (int k = j + 1; k < partyNum; k++) {
                    g.get(temp[j]).add(temp[k]);
                    g.get(temp[k]).add(temp[j]);
                }
            }
        }

        for(int i = 1; i <= n; i++) {
            if(knowPerson[i]){
            	  //내부 bfs 돌리면서 진실 앎 표기
                bfs(i);
            }
        }


//        for(int i = 0 ; i <= n; i++){
//            System.out.print(knowPerson[i] + " ");
//        }
//        System.out.println();

        for(int i = 0 ; i <m ; i++){
            boolean flag = false;

            for(int num : parties.get(i)){
                if(knowPerson[num]){
                    flag = true;
                    break;
                }
            }
            //진실을 모르는 사람만 속한 파티일때 answer++;
            if(!flag){
                answer++;
            }
        }


        writer.write(answer + " ");
        writer.flush();
        writer.close();
    }

    static void bfs(int start){
        ArrayDeque<Integer> que = new ArrayDeque<>();
        que.add(start);

        while(!que.isEmpty()) {
            int pre = que.poll();
            for(int now : g.get(pre)){
                if(!knowPerson[now]){
                    knowPerson[now] = true;
                    que.add(now);
                }
            }
        }
    }
}