[백준] 1043번 - 거짓말 (Gold 4)

문제 링크

백준 1043번 - 거짓말 (Gold 4)

문제 설명

파티에서 다음 두 가지 조건을 만족하면서 거짓말을 최대한 많이 하고자 한다.

• 한 명이 어떤 파티에서는 진실을, 어떤 파티에서는 거짓말을 듣는 경우는 없어야 한다.
• 처음부터 진실을 알고 있던 사람이 있는 파티에서 거짓말을 해서도 안된다.

이 때, 거짓말을 할 수 있는 최대 횟수를 구하면 된다.

정답 코드 및 설명

처음부터 진실을 알고 있던 사람들로 시작해서, 같은 파티에 참석하는 사람들은 모두 진실을 들어야 한다.
이를 구현하기 위해 파티의 참가자 목록과 사람들이 참가한 파티 목록을 둘 다 저장하였다.
처음부터 진실을 알고 있던 사람들이 참가한 파티들로 시작해서 BFS를 수행한다.
같은 파티에 있는 사람들을 모두 연결된 것으로 취급하면 된다.
파티나 사람은 한번만 체크하면 충분하므로, 각각을 체크하기 위한 변수도 사용한다.

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

public class Main {

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

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        Party party = new Party(n, m);
        // 진실을 알고 있는 사람의 목록 = personTrue
        st = new StringTokenizer(br.readLine());
        int numTrue = Integer.parseInt(st.nextToken());
        int[] personTrue = new int[numTrue];
        for (int i = 0; i < numTrue; i++)
            personTrue[i] = Integer.parseInt(st.nextToken()) - 1;
        // partyList[], party[] 만들기
        for (int i = 0; i < m; i++) {
            party.party[i] = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            int partyPeople = Integer.parseInt(st.nextToken());
            for (int j = 0; j < partyPeople; j++) {
                int person = Integer.parseInt(st.nextToken()) - 1;
                party.partyList[person].add(i);
                party.party[i].add(person);
            }
        }
        bw.write(max(personTrue, party) + "");
        bw.close();
    }

    static int max(int[] personTrue, Party party) {
        int max = party.m;
        boolean[] checkPerson = new boolean[party.n]; // 사람 체크
        boolean[] checkParty = new boolean[party.m]; // 파티 체크
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < personTrue.length; i++) {
            queue.add(personTrue[i]);
            checkPerson[personTrue[i]] = true;
        }
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            // 진실을 알게 된 사람이 참가한 파티 목록
            Iterator<Integer> iter = party.partyList[curr].iterator();
            while (iter.hasNext()) {
                int partyIndex = iter.next();
                // 이미 체크한 파티면 스킵
                if (checkParty[partyIndex])
                    continue;
                checkParty[partyIndex] = true;
                max--; // 거짓을 말할 수 없는 파티이므로 max 1 감소
                // 파티에 같이 참가한 사람들 체크
                Iterator<Integer> iter2 = party.party[partyIndex].iterator();
                while (iter2.hasNext()) {
                    int person = iter2.next();
                    if (checkPerson[person])
                        continue;
                    checkPerson[person] = true;
                    queue.add(person);
                }
            }
        }
        return max;
    }
}

class Party {
    ArrayList<Integer> partyList[], party[];
    int n, m;

    Party(int n, int m) {
        partyList = new ArrayList[n];
        for (int i = 0; i < n; i++)
            partyList[i] = new ArrayList<>();
        party = new ArrayList[m];
        for (int i = 0; i < m; i++)
            party[i] = new ArrayList<>();
        this.n = n;
        this.m = m;
    }
}

나중에 찾아본 결과, 이 문제는 분리 집합 문제로, Union-Find라는 알고리즘으로 푼다고 한다.
현재는 이 쪽에 대해서는 아는게 아예 없으니, 추후에 공부해서 다시 풀어봐야겠다.