[1043] 거짓말

✔ 거짓말

[백준 1043]

문제 분석하기

각각의 파티마다 union 연산을 이용해 1개의 집합으로 연결한 후,

각 파티의 대표 노드와 진실을 알고 있는 사람들의 각 대표 노드가 동일한지 find 연산을 이용해 확인함으로써 판단

손으로 풀어보기

1. 진실을 아는 사람 데이터, 파티 데이터, 유니온 파인드를 위한 대표 노드 자료구조를 초기화
2. union 연산을 수행해 각 파티에 참여한 사람들을 1개의 그룹으로 만듦
3. find 연산을 수행해 각 파티의 대표 노드와 진실을 아는 사람들이 같은 그룹에 있는지 확인
4. 모든 파티의 대표 노드가 진실을 아는 사람들과 다른 그룹에 있다면 결괏값을 증가시킴
5. 과장할 수 있는 파티의 개수를 결괏값으로 출력

예) 8명의 사람, 5개의 파티

진실을 아는 사람 - 3명 : 1, 2, 7

파티 1 - 2명 : 3, 4

파티 2 - 1명 : 5

파티 3 - 2명 : 5, 6

파티 4 - 2명 : 6, 8

파티 5 - 1명 : 8

1	2	3	4	5	6	7	8
1	2	3	4 → 3	5	6 → 5	7	8 → 5

1번째 파티 (3, 4) = find(3) = 3이므로 과장할 수 있음 (1, 2, 7이 아님)

2번째 파티 (5) = find(5) = 5이므로 과장할 수 있음 (1, 2, 7이 아님)

3번째 파티(5, 6) = find(5) = 5이므로 과장할 수 있음 (1, 2, 7이 아님)

4번째 파티(6, 8) = find(6) = 5이므로 과장할 수 있음 (1, 2, 7이 아님)

5번째 파티(8) = find(8) = 5이므로 과장할 수 있음 (1, 2, 7이 아님)

슈도코드 작성하기

N(사람 수) M(파티 개수)
T(진실을 아는 사람) trueP(진실을 아는 사람 데이터) party(파티 데이터)
parent(대표 노드 저장 배열)
데이터를 입력받아 각자 자료구조에 저장하기
for(N만큼 반복하기) {
    대표 노드를 자기 자신으로 초기화하기
}
for(i -> M만큼 반복하기) {
    firstPeople(i번째 파티의 1번째 사람) 
    for(j -> i번째 파티의 사람 수만큼 반복하기) {
        union(firstPeople, j)
    }
}
for(i -> M만큼 반복하기) {
    firstPeople(i번째 파티의 사람)
    for(j -> 진실을 아는 사람들의 수만큼 반복하기) {
        find(firstPeople), find(trueP[j]) 비교하기
    }
    모두 다른 경우 결괏값 1 증가
}
결괏값 출력하기
union(a, b) {
    a와 b의 대표 노드 찾기
    두 원소의 대표 노드끼리 연결하기
}
find(a, b) {
    a가 대표 노드면 리턴
    아니면 a의 대표 노드값을 find(parent[a])값으로 저장 -> 재귀 함수 형태
}

코드 구현하기

/**
 * 1043) 거짓말
 */
public class D052_1043 {
    static int[] parent;
    static int[] trueP;
    static ArrayList<Integer>[] party;
    static int result;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(사람 수)
        int N = sc.nextInt();
        // M(파티 개수)
        int M = sc.nextInt();
        // T(진실을 아는 사람)
        int T = sc.nextInt();
        result = 0;
        // trueP(진실을 아는 사람 데이터)
        trueP = new int[T];
        // 진실을 아는 사람 저장하기
        for (int i = 0; i < T; i++) {
            trueP[i] = sc.nextInt();
        }
        // party(파티 데이터)
        party = new ArrayList[M];
        // 파티 데이터 저장하기
        for (int i = 0; i < M; i++) {
            party[i] = new ArrayList<Integer>();
            int party_size = sc.nextInt();
            for (int j = 0; j < party_size; j++) {
                party[i].add(sc.nextInt());
            }
        }
        // parent(대표 노드 저장 배열)
        parent = new int[N + 1];
        // 대표 노드를 자기 자신으로 초기화하기
        for (int i = 0; i <= N; i++) {
            parent[i] = i;
        }
        // 각 파티에 참여한 사람들을 1개의 그룹으로 만들기
        for (int i = 0; i < M; i++) {
            // firstPeople(i번째 파티의 1번째 사람)
            int firstPeople = party[i].get(0);
            for (int j = 1; j < party[i].size(); j++) {
                union(firstPeople, party[i].get(j));
            }
        }
        for (int i = 0; i < M; i++) {
            boolean isPossible = true;
            // firstPeople(i번째 파티의 사람)
            int firstPeople = party[i].get(0);
            for (int j = 0; j < trueP.length; j++) {
                // 각 파티의 대표 노드와 진실을 아는 사람들의 노드가 같다면 과장할 수 없음
                if (find(firstPeople) == find(trueP[j])) {
                    isPossible = false;
                    break;
                }
            }
            // 모두 다른 경우 결괏값 1 증가
            if (isPossible)
                result++;
        }
        System.out.println(result);
    }

    // union 연산
    public static void union(int a, int b) {
        // a와 b의 대표 노드 찾기
        a = find(a);
        b = find(b);
        // 두 원소의 대표 노드끼리 연결하기
        if (a != b) {
            parent[b] = a;
        }
    }

    // find 연산
    public static int find(int a) {
        // a가 대표 노드면 리턴
        if (a == parent[a]) {
            return a;
        }
        // 아니면 a의 대표 노드값을 find(parent[a]) 값으로 저장 -> 재귀 함수 형태
        else {
            return parent[a] = find(parent[a]);
        }
    }
}