[백준] 1043 : 거짓말 (JAVA/자바)

문제

BOJ 1043 : 거짓말 - https://www.acmicpc.net/problem/1043

풀이

input을 받으면서부터 엄청 헷갈렸던 문제다. n과 m이 주어진 뒤, 진실을 알고있는 사람 정보가 주어지고, 각 파티별 참석자 정보가 주어진다.

진실을 알고있는 사람(A)과 같은 파티에 참석한 진실을 모르는 사람(B) 또한 진실을 듣게 된다. 그래서 이 진실을 모르지만 진실을 듣게된 사람(B)이 모든 사람이 진실을 모르는 파티에 가게 된다면, 모든 사람이 진실을 알지 못하지만 그 파티에서는 과장되게 말할 수 없다. B가 다른 파티에서 진실을 들었기 때문에 모순이 생기기 때문이다.

1. 우선 input을 받으며 파티 참석자의 정보를 저장하고, 파티 참석자 간 연관 관계를 나타내야했다. 그래프를 전부 그리기 보다는 각각의 사람이 연관관계가 있는지만 판단하면 됐기 때문에 union-find를 활용해서 parent 정보를 저장했다. (같은 parent를 가지면 이어져 있는 것으로 판단)

2. 이후 진실을 아는 사람과 연관되어있다는 것은 진실을 듣는다는 것이기 때문에 각각 파티에서 진실을 듣는지, 과장된 이야기를 듣는지를 저장해둔다.

3. 각 파티 별 참석자를 확인한다. 진실된 이야기를 들어야하는 사람이 한명이라도 있다면 패스하고, 아니라면 그 파티에서는 과장된 이야기를 할 수 있기 때문에 카운트 해준다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {

    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");

        int n = Integer.parseInt(inputs[0]);
        int m = Integer.parseInt(inputs[1]);

        boolean[] people_know = new boolean[n+1]; // 알고있으면 T, 아니면 F

        HashSet<Integer>[] parties = new HashSet[m+1];
        for (int i = 1; i <= m; i++) {
            parties[i] = new HashSet<>();
        }

        inputs = br.readLine().split(" ");
        int know_num = Integer.parseInt(inputs[0]);

        for (int i = 1; i <= know_num; i++) { // 진실을 아는사람 T
            int tmp = Integer.parseInt(inputs[i]);
            people_know[tmp] = true;
        }

        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        for (int p = 1; p <= m; p++) { // party number

            inputs = br.readLine().split(" ");
            int party_num = Integer.parseInt(inputs[0]); // 파티에 오는 사람 수

            if(party_num<=1) {
                parties[p].add(Integer.parseInt(inputs[1]));
                continue;
            }

            for (int j = 1; j < party_num; j++) { // 연관 관계 이어줌
                int a = Integer.parseInt(inputs[j]);
                int b = Integer.parseInt(inputs[j+1]);
                if (find(a) != find(b)) {
                    union(a,b);
                }

                parties[p].add(a); // 파티에 참여하는 사람 저장
                parties[p].add(b);
            }
        }

        // 진실을 아는 사람과 연관 관계 있음 => people_know[i] T로 변경
        boolean[] visited = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            if(people_know[i] && !visited[i]){
                int root = find(i);
                for (int j = 1; j <= n; j++){
                    if (find(j)==root) {
                        people_know[j] = true;
                        visited[j] = true;
                    }
                }
            }
        }

        // 모든 파티 참석자가 F여야 과장된 얘기를 할 수 있음
        int result = 0;
        for (int i = 1; i <= m; i++) { // party
            boolean flag = false;
            for (int person : parties[i]) { // 참석자
                if(people_know[person]){
                    flag = true;
                    break;
                }
            }
            if(!flag) result++;
        }

        System.out.println(result);
    }

    public static int find(int idx) {
        if(parent[idx]==idx){
            return idx;
        }
        parent[idx] = find(parent[idx]);
        return parent[idx];
    }

    public static void union(int a, int b) {
        int parent_b = find(b);
        parent[parent_b] = a; // b의 parent를 a로 변경
    }

}

정리

✔ 알고리즘 분류 - 그래프 이론, 자료 구조, 그래프 탐색, 분리 집합
✔ 난이도 - 🟡 Gold 4

🤦‍♀️ 오늘의 메모

• 정리하고 보니 별거 아닌데, 조건이 너무 헷갈려서 자꾸 멍해지는 문제였다. 연관 관계를 저장하는 방법과, 그 연관 관계를 중심으로 진실을 듣는 사람인지 판단하는 로직에서 많이 헷갈렸다. union-find가 이런 식으로 쓰일 수도 있다는 걸 잘 기억해두기!

참고 사이트

딱히없음