문제

https://www.acmicpc.net/problem/1043

Gold IV

코드(Java)

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

public class Main {
    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());
        boolean[] know_truth = new boolean[N+1];
        boolean[][] came_to_party = new boolean[M][N+1];

        //initial people who know truth
        st = new StringTokenizer(br.readLine());
        int init_know_cnt = Integer.parseInt(st.nextToken());
        for (int i = 0; i < init_know_cnt; ++i) {
            int knower = Integer.parseInt(st.nextToken());
            know_truth[knower] = true;
        }

        //obtain party data
        for (int i = 0; i < M; ++i) {
            st = new StringTokenizer(br.readLine());
            int participants = Integer.parseInt(st.nextToken());
            for (int j = 0; j < participants; ++j) {
                came_to_party[i][Integer.parseInt(st.nextToken())] = true;
            }
        }

        //obtain final truth knowers
        while (true) {
            boolean modified = false;
            for (int i = 0; i < M; ++i) {
                if (came_to_party[i][0]) continue;
                boolean exist_knower = false;
                for (int j = 1; j <= N; ++j) {
                    if (came_to_party[i][j] && know_truth[j]) {
                        exist_knower = true;
                        break;
                    }
                }

                if (exist_knower) {
                    came_to_party[i][0] = true;
                    for (int j = 1; j <= N; ++j) {
                        if (came_to_party[i][j]) {
                            if (!know_truth[j]) modified=true;
                            know_truth[j] = true;
                        }
                    }
                }
            }
            if (!modified) break;
        }

        //check which party we can lie
        int cnt = 0;
        for (int i = 0; i < M; ++i) {
            if (!came_to_party[i][0]) ++cnt;
        }

        System.out.print(cnt);
    }
}

풀이

제한조건 최대값이 작어서 반복을 여러번 해도 별 문제 없다고 판단...해가지고 브루트포스로 풀었다고 해야하나?

분류를 보니까 그래프로 푸는 방법도 있고 유니온 파인드로 푸는 방법도 있는것 같은데 잘 모르겠다. 나중에 풀이 보고 확인해볼 예정.

여튼 방법은

1. 초기 진실을 알고 있는 사람들 추적, know_truth에 표기.

2. 파티 정보 습득. (각 파티별 참가여부)

3. know_truth에 변동이 없을 때까지 반복해서 거짓말을 못하는 파티를 찾아본다. 처음에는 한번만 탐색했는데 꼬리에 꼬리를 무는 형태로 데이터가 존재하면 이를 잘 못 추적했다. 예를 들면 밑의 예시. 답은 0이다.

4 3
1 1
2 1 2
2 2 3
2 3 4

4. came_to_party의 각 행의 0번째 index를 가지고 진실을 아는 자가 있는지 여부를 확인. 그 개수를 세가지고 거짓말할 수 있는 파티 개수를 구함.