업데이트:

문제 링크

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

문제 설명

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

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

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

정답 코드 및 설명

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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라는 알고리즘으로 푼다고 한다.
현재는 이 쪽에 대해서는 아는게 아예 없으니, 추후에 공부해서 다시 풀어봐야겠다.

태그: ,

카테고리:

업데이트:

댓글남기기