백준 - 거짓말

문제 링크 ▶︎ 거짓말

문제 파악

처음에는 각 파티에 참여한 사람의 정보를 받은 배열을 순회하면서 진실을 아는 사람과 함께 파티에 참석한 사람을 진실을 안다고 바꿔주는 식으로 생각했는데, 더이상의 전파가 없을 때까지 반복해서 하는 작업이 구현이 더 어려울 것 같아서 bfs로 진실을 아는 사람과 함께 참석했으면 전파하는 식으로 생각했다.

각 노드를 양방향 연결한다고 생각하고 진실을 아는 사람과 연결된 사람을 모두 진실을 아는 것으로 바꿔주면 된다.

접근 방법

1. Map<Integer, Set> 로 만든 자료구조는 각 사람마다 파티에 누구와 같이 참석했는지에 대한 정보를 나타낸다. 1번의 키값은 1번이 참석한 파티에 같이 참석한 사람이 된다. 이는 양방향으로 저장되기 때문에 모두 연결되어있다.

2. 처음 진실을 아는 사람의 정보를 받고, boolean 배열에 각 사람의 인덱스에 진실을 알면 true로 저장한다.

3. bfs로 진실을 아는 사람과 연결된 사람을 모두 boolean true로 바꿔 진실을 안다고 바꿔놓는다. 모든 순회가 돌면 이제 진실을 아는 사람이 모두 설정되게 된다.

4. 이후 모든 파티를 순회하면서 진실을 아는 사람이 1명이라도 없는 파티에만 거짓말을 할 수 있기 때문에 그 조건에서만 answer++을 한다.

코드 구현

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

public class Main {
    public static int n;
    public static int m;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        boolean[] peoples = new boolean[n+1];
        Map<Integer, Set<Integer>> relation = new HashMap<>();
        st = new StringTokenizer(br.readLine());
        int len = Integer.parseInt(st.nextToken());
        int[] known = new int[len];
        for (int i = 0; i < len; i++) {
            known[i] = Integer.parseInt(st.nextToken());
            peoples[known[i]] = true;
        }
        for (int i = 1; i <= n; i++) {
            relation.put(i, new HashSet<>());
        }
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int cnt = Integer.parseInt(st.nextToken());
            int[] temp = new int[cnt];
            for (int j = 0; j < cnt; j++) {
                temp[j] = Integer.parseInt(st.nextToken());
            }
            list.add(temp);
            if (cnt > 1) {
                for (int j = 0; j < cnt - 1; j++) {
                    for (int k = j + 1; k < cnt; k++) {
                        relation.get(temp[j]).add(temp[k]);
                        relation.get(temp[k]).add(temp[j]);
                    }
                }
            }
        }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            q.add(known[i]);
        }
        while (!q.isEmpty()) {
            int out = q.remove();
            if (!peoples[out]) {
                continue;
            }
            for (int next : relation.get(out)) {
                if (!peoples[next]) {
                    q.add(next);
                    peoples[next] = true;
                }
            }
        }
        int answer = 0;
        for (int i = 0; i < m; i++) {
            boolean isvalid = false;
            for (int p : list.get(i)) {
                if (peoples[p]) {
                    isvalid = true;
                    break;
                }
            }
            if (!isvalid) {
                answer++;
            }
        }
        System.out.println(answer);
    }
}

개선 사항

bfs로 그래프 개념을 활용해서 푸는 것도 괜찮은 방법이고, 진실을 아는 것이 모두 전파된 순간까지 while 문으로 푸는 것도 좋은 방법인 것 같다.