[백준][Gold IV] Java - 1043번 : 거짓말

□ 문제 : 최대 거짓말 가능 회수를 카운트하는 프로그램 구현

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

• 진실을 아는 사람이 없는 경우 파티 수 만큼 거짓말 가능
• 진실을 아는 사람이 있는 경우 전염되어 거짓말을 할 수 있는 파티 수가 줄어듬
  ex)
  진실을 아는사람 (1)이 있다고 가정
  4번 파티에 진실을 아는사람(1)과 모르는 사람(2)가이 있고
  3번 파티에 (2)와 다른 모르는 사람(3)이 있다면 지민이는 3번 파티에서도 거짓말을 할 수 없게됨

□ 사용 알고리즘

• BFS

□ 전체 코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    static int N, M, P;
    static HashMap<Integer, Integer> trueP;
    static List<int[]> partyList = new ArrayList<>();
    static int[] party;
    static int count = 0;
    static boolean[] visit;
    static Queue<int[]> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {

        // 변수들 입력 받기
        input();

        // 진실을 아는 사람이 없는 경우 파티 수 만큼 리턴
        if (P == 0) {
            bw.write(Integer.toString(M));
            bw.flush();
            return;
        }

        // 파티 생성
        for (int i = 0; i < M; i++) {
            party(i);
        }

        // 진실을 아는 사람 겹치는 파티 체크
        BFS();

        // 파티를 순회하며 처리
        for (int[] party : partyList) {
            search(party);
        }

        bw.write(Integer.toString(count));
        bw.flush();
    }

    static void input() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        visit = new boolean[M];

        st = new StringTokenizer(br.readLine());
        P = Integer.parseInt(st.nextToken());
        if (P != 0) {
            trueP = new HashMap<>();
            for (int i = 0; i < P; i++) {
                trueP.put(Integer.parseInt(st.nextToken()), 0);
            }
        }
    }

    static void party(int index) throws IOException {
        st = new StringTokenizer(br.readLine());
        int p = Integer.parseInt(st.nextToken());
        party = new int[p];
        boolean flag = false;

        for (int i = 0; i < p; i++) {
            party[i] = Integer.parseInt(st.nextToken());
            if (trueP.containsKey(party[i])) {
                flag = true;
            }
        }

        if (flag) {
            q.add(party);
            visit[index] = true;
        }

        partyList.add(party);
    }

    static void BFS() {
        while (!q.isEmpty()) {
            int[] nowParty = q.poll();
            for (int i : nowParty) {
                if (!trueP.containsKey(i)) trueP.put(i, 0);
            }

            for (int i = 0; i < partyList.size(); i++) {
                if (!visit[i]) {
                    int[] nextParty = partyList.get(i);
                    for (int p : nextParty) {
                        if (trueP.containsKey(p)) {
                            q.add(nextParty);
                            visit[i] = true;
                        }
                    }
                }
            }
        }
    }

    static void search(int[] party) {
        for (int i : party) {
            if (trueP.containsKey(i)) return;
        }

        count++;
    }
}

 

□ 풀이 과정

0. main 함수

public static void main(String[] args) throws IOException {

        // 변수들 입력 받기
        input();

        // 진실을 아는 사람이 없는 경우 파티 수 만큼 리턴
        if (P == 0) {
            bw.write(Integer.toString(M));
            bw.flush();
            return;
        }

        // 파티 생성
        for (int i = 0; i < M; i++) {
            party(i);
        }

        // 진실을 아는 사람 겹치는 파티 체크
        BFS();

        // 파티를 순회하며 처리
        for (int[] party : partyList) {
            search(party);
        }

        bw.write(Integer.toString(count));
        bw.flush();
    }

 

1. 변수 값 입력 받기 - input()

static void input() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        visit = new boolean[M];

        st = new StringTokenizer(br.readLine());
        P = Integer.parseInt(st.nextToken());
        if (P != 0) {
            trueP = new HashMap<>();
            for (int i = 0; i < P; i++) {
                trueP.put(Integer.parseInt(st.nextToken()), 0);
            }
        }
    }

 

2. 입력받은 변수에서 진실을 아는사람(P) 가 0인 경우 파티 수(M)만큼 결과 반환 프로그램 종료

  if (P == 0) {
            bw.write(Integer.toString(M));
            bw.flush();
            return;
        }

 

3. party 생성 - party(int index)

static void party(int index) throws IOException {
        st = new StringTokenizer(br.readLine());
        int p = Integer.parseInt(st.nextToken());
        party = new int[p];
        boolean flag = false;

        for (int i = 0; i < p; i++) {
            party[i] = Integer.parseInt(st.nextToken());
            if (trueP.containsKey(party[i])) {
                flag = true;
            }
        }

        if (flag) {
            q.add(party);
            visit[index] = true;
        }

        partyList.add(party);
    }

• main함수에서 party()함수를 호출 할 때 for문을 통해 index를 함께 전달
• 만약 party안에 진실을 아는 사람이 있는 경우 큐에 추가 및 전달받은 index로 방문처리
• 생성된 party는 list에 추가해줌(list의 index를 활용)

4. 진실을 아는 사람의 겹침을 확인하여 추가하는 함수 - BFS()

static void BFS() {
        while (!q.isEmpty()) {
            int[] nowParty = q.poll();
            for (int i : nowParty) if (!trueP.containsKey(i)) trueP.put(i, 0);

            for (int i = 0; i < partyList.size(); i++) {
                if (!visit[i]) {
                    int[] nextParty = partyList.get(i);
                    for (int p : nextParty) {
                        if (trueP.containsKey(p)) {
                            q.add(nextParty);
                            visit[i] = true;
                        }
                    }
                }
            }
        }
    }

• 파티 생성 시 추가 큐에 추가된 배열부터 시작하여 partyList를 순회하며 겹치는 파티 모두 확인

5. 모든 파티를 순회 하며 진실을 아는 사람이 포함되지 않은 파티에 대해서 count를 증가

    static void search(int[] party) {
        for (int i : party) {
            if (trueP.containsKey(i)) return;
        }

        count++;
    }