[백준] no1043: 거짓말 - 그래프 탐색

문제

* 1. 총 인원 수 만큼 boolean형 배열을 만듦 (전부 false)
* 2. 그 중 진실을아는사람은 true로 변경
* 3. 모든 파티를 돌면서, 해당 파티에 true인 인원이 있으면, 해당 파티의 모든 인원을 true로 변경
* 4. 모든 파티를 돌면서, 해당 파티에 true인 인원이 없으면, count++
* 5. count 출력

문제 링크 : https://www.acmicpc.net/problem/1043

---

원리

그래프 탐색 또는 DP

---

풀이방법

1. 필자의 경우 브루트포스(?) 방식으로 풀어보려했다.

2. Chat GPT는 전형적인 DP로 풀이했다.

3. 레퍼런스 코드의 경우 그래프 탐색을 이용했다.

 

---

나의 코드

[실패] 풀이 자체엔 문제가 없다.

Chat GPT 상으로도 문제가 없는 코드로 판명되었다. 그러나 백준에서 통과가 되지않는다.

import java.io.*;
import java.util.*;

public class no1043 {
    private static int people;
    private static int partys;
    private static int known;
    private static int cnt = 0;
    private static boolean[] knowns;
    private static boolean[][] partyTable;

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

        // 첫 번째 줄 : 사람의 수와 파티의 수
        StringTokenizer firstLine = new StringTokenizer(br.readLine(), " ");
        people = Integer.parseInt(firstLine.nextToken());
        partys = Integer.parseInt(firstLine.nextToken());
        knowns = new boolean[people+1];

        // 두 번째 줄 : 진실을 아는 사람 수, 만약 있으면 진실을 아는 사람 수만큼 리스트에 추가
        StringTokenizer secondLine = new StringTokenizer(br.readLine(), " ");
        known = Integer.parseInt(secondLine.nextToken());
        for(int i=0; i<known ; i++) knowns[Integer.parseInt(secondLine.nextToken())] = true;

        partyTable = new boolean[partys][people+1];

        //
        for(int i=0 ; i<partys ; i++) {
            StringTokenizer partyLine = new StringTokenizer(br.readLine(), " ");

            // 각 파티당 참석 인원수
            int partyMember = Integer.parseInt(partyLine.nextToken());

            // 만약 이번 파티에 진실을 아는 사람이 있는 경우 true 체크하여 이번 파티에 모인 사람들을 전부 진실을 알게 해주기위함
            boolean check = false;

            // 각 파티당 멤버가 누구였는지 체크
            for(int j=0 ; j<partyMember ; j++) {
                int nowMember = Integer.parseInt(partyLine.nextToken());
                partyTable[i][nowMember] = true;
                if(knowns[nowMember]) check = true;
            }

            // 이번 파티에 진실을 아는 사람이 있을 경우, 참석자 전원 진실을 알게됨
            if(check) {
                for(int j=1 ; j<=people ; j++) {
                    if(partyTable[i][j]) knowns[j] = true;
                }
            }
        }

        // 각 파티 테이블을 돌면서, 해당 파티의 참석자 전원이 진실을 모를 경우 cnt++
        for(int i=0 ; i<partys ; i++) {
            for(int j=1 ; j<=people ; j++) {
                if(partyTable[i][j] && knowns[j]) break;  // j번의 사람이 참석했고, 진실을 알 경우 이 파티는 조진거
                if(j==people) cnt++; // 끝까지 확인해봤는데 아무도 모르면 야부리 터는거
            }
        }

        System.out.println(cnt);
    }
}

---

Chat GPT 코드

답없음. 이새기 거짓말하면서 계속 안풀리니까 나한테 시킴.

결국 끝까지 못풂.

 

그 와중에 말대답은 개잘함

Chat 재민이의 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

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

        int[] truth = new int[51];
        int truthNum = sc.nextInt();
        for (int i = 0; i < truthNum; i++) {
            truth[i] = sc.nextInt();
        }

        List<Integer>[] party = new ArrayList[m];
        for (int i = 0; i < m; i++) {
            party[i] = new ArrayList<>();
            int num = sc.nextInt();
            for (int j = 0; j < num; j++) {
                party[i].add(sc.nextInt());
            }
        }

        for (int i = 0; i < m; i++) {
            List<Integer> p = party[i];
            for (int j = 0; j < p.size(); j++) {
                int a = p.get(j);
                for (int k = j + 1; k < p.size(); k++) {
                    int b = p.get(k);
                    int pa = find(parent, a);
                    int pb = find(parent, b);
                    if (pa != pb) {
                        parent[pb] = pa;
                    }
                }
            }
        }

        int count = 0;
        for (int i = 0; i < m; i++) {
            List<Integer> p = party[i];
            boolean flag = true;
            for (int j = 0; j < p.size(); j++) {
                int a = p.get(j);
                if (Arrays.binarySearch(truth, 0, truthNum, find(parent, a)) >= 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                count++;
            }
        }

        System.out.println(count);
    }

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

---

레퍼런스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int[] parent;

    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());

        st = new StringTokenizer(br.readLine());
        int knowNum = Integer.parseInt(st.nextToken());
        boolean[] knowPeople;

        //진실을 아는 사람이 없다면 파티의 수를 출력하고 바로 종료
        if(knowNum == 0){
            System.out.println(M);
            return;
        }
        //자신과 연결된 루트 노드를 설정
        parent = new int[N+1];
        for(int i = 1; i<=N; i++)
            parent[i] = i;

        //진실을 아는 사람들의 배열을 생성
        knowPeople = new boolean[N+1];
        for(int i = 0; i<knowNum; i++) {
            int num = Integer.parseInt(st.nextToken());

            knowPeople[num] = true;
        }

        //파티마다 참여한 사람들의 목록을 생성
        List<List<Integer>> partyList = new ArrayList<>();
        for(int i = 0; i<M; i++)
            partyList.add(new ArrayList<>());

        for(int i = 0; i<M; i++){
            st = new StringTokenizer(br.readLine());

            int num = Integer.parseInt(st.nextToken());
            for(int j = 0; j<num; j++) {
                partyList.get(i).add(Integer.parseInt(st.nextToken()));

                //같이 파티에 참가한 사람을 확인
                if(j != 0){
                    int nowIdx = partyList.get(i).get(j);
                    int exIdx = partyList.get(i).get(j-1);

                    union(exIdx, nowIdx);
                }
            }
        }

        boolean[] visited = new boolean[N+1];
        for(int i = 1; i<=N; i++){
            if(knowPeople[i] && !visited[i]) {
                int root = find(i);

                for (int j = 1; j <= N; j++) {
                    if(find(j) == root){
                        knowPeople[j] = true;
                        visited[j] = true;
                    }
                }
            }
        }

        //파티에 진실을 아는 사람이 있는지 확인
        boolean[] goParty = new boolean[M];
        for(int i = 0; i<M; i++)
            goParty[i] = true;

        for(int i = 0; i<M; i++){
            for(int j = 1; j<=N; j++){
                if(knowPeople[j]){
                    if(partyList.get(i).contains(j))
                        goParty[i] = false;
                }
            }
        }

        int sum = 0;
        for(int i = 0; i<M; i++)
            if(goParty[i])
                sum++;

        System.out.println(sum);
    }

    //자신과 연결된 노드의 루트 노드를 탐색
    static int find(int idx){
        if(parent[idx] == idx)
            return idx;
        else {
            parent[idx] = find(parent[idx]);
            return parent[idx];
        }
    }

    //연결된 노드가 다르다면 연결해줌
    static void union(int idx1, int idx2){
        int parent1 = find(idx1);
        int parent2 = find(idx2);

        if(parent1 != parent2)
            parent[parent2] = parent1;
    }
}