백준 1043 Java 풀이

[1043-거짓말]

문제

• N 사람의 수 ( 1 <= N <= 50 )
• M 파티의 수 ( 1 <= N <= 50 )
• 진실을 아는 사람이 주어졌을때 거짓말을 할 수 있는 파티의 수를 구하는 문제
• 파티에 참석하는 인원이 주어진다.

풀이

• 진실을 아는 사람들이 존재하는 파티, 그 파티에 참석하는 인원들을 모두 합집합 연산하여 해결할 수 있다. Union Find
• 처리 순서는 아래와 같다.

1. 같은 파티에 참석하는 인원들이 같은 부모를 바라보도록 처리해준다 (Union)

2. 진실을 아는 사람들의 부모 노드를 파악하여 해당 부모 노드를 갖는 노드들을 모두 진실을 아는 사람들로 처리해준다.

3. 파티에 진실을 아는 사람이 없을 경우 결과값을 증가시켜 준다.

• 진실을 아는 사람이 1, 2고 각 파티에 참여하는 사람들이 그림과 같을때 parents 배열의 union 과정이다. 합집합된 결과 배열은 실제로는 아래와 같을 것이다. (1번 과정)

• 그후 진실을 아는 사람들의 배열 truth[]에 true인 Index의 부모 노드를 찾아 해당 노드를 부모노드로 갖는 모든 Index를 true로 바꿔준다. (2번 과정)

• 파티를 순회하며 진실을 아는 사람이 있는지 확인 후 결과값을 증가시켜 준다.

코드

• 입력값과 초기 선언문 때문에 코드가 길지만 위에 풀이한 순서대로 보면 어렵지 않음.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;


public class Main {
    private static int[] parents;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        parents = new int[n + 1];
        boolean[] truth = new boolean[n + 1];
        boolean[] visited = new boolean[n + 1];
        List<Integer>[] parties = new List[m];
        int result = 0;

        for (int i = 0 ; i <= n ; i++) {
            parents[i] = i;
        }

        for (int i = 0 ; i < m ; i++) {
            parties[i] = new ArrayList<>();
        }

        st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());

        for (int i = 0 ; i < k ; i++) {
            int member = Integer.parseInt(st.nextToken());
            truth[member] = true;
        }

		//1번 과정
        for (int i = 0 ; i < m ; i++) {
            st = new StringTokenizer(br.readLine());
            int members = Integer.parseInt(st.nextToken());

            int member = Integer.parseInt(st.nextToken());
            parties[i].add(member);

            for (int j = 1 ; j < members ; j++) {
                int nextMember = Integer.parseInt(st.nextToken());

                if (find(member) != find(nextMember)) {
                    union(member, nextMember);
                }

                parties[i].add(nextMember);
            }
        }

		//2번 과정
        for (int i = 1 ; i <= n ; i++) {
            if (truth[i] && !visited[i]) {
                int parent = find(i);
                for (int j = 1 ; j <= n ; j++) {
                    if (find(j) == parent) {
                        truth[j] = true;
                        visited[j] = true;
                    }
                }
            }
        }

		//3번 과정
        for (int i = 0 ; i < m ; i++) {
            boolean flag = false;

            for (int num : parties[i]) {
                if (truth[find(num)]) {
                    flag = true;
                    break;
                }
            }

            if (!flag) {
                result++;
            }
        }

        System.out.println(result);
    }

    private static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        parents[rootB] = rootA;
    }

    private static int find(int n) {
        if (parents[n] == n) {
            return n;
        }
        return parents[n] = find(parents[n]);
    }
}