[백준]1042: 거짓말 - JAVA

[백준]1042: 거짓말

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

1043번: 거짓말

풀이

🪑 문제를 따라 조건들을 차례차례 정리해 보았다.

• 지민 -> 진실 OR 과장(되도록 과장 BUT 거짓말 들키기 싫어함)
• 진실 아는 사람 존재 -> 과장 할 수 없음.
• 진실을 한 번 이라도 들은 사람은 진실을 아는 사람이다.

 

🔧 위의 조건들을 토대로 어떻게 풀지 풀이 순서를 적어보았다.

1. 진실을 아는 사람들의 정보를 모은다.
2. 진실을 아는 사람이 속해있는 파티를 조사하여 해당 파티원들을 전부 진실을 아는 사람들의 정보에 추가한다.
3. 이미 진실을 아는 사람이거나, 이미 확인한 파티는 조사하지 않는다.

 

위의 방식대로 하나씩 구현해 나가 보자!

 

🔹 진실을 아는 사람들의 정보를 모은다.

- 진실을 아는 사람들의 정보를 입력 받을때면서 리스트에 저장해 주었다.

 

🔹 진실을 아는 사람이 속해있는 파티를 조사하여 해당 파티원들을 진실을 아는 사람들의 정보에 추가한다.

- BFS 탐색을 사용하였다. 해당 코드는를 구현하고 보니 위상정렬 코드와 유사하게 구현하였다.

- 먼저, 큐에 진실을 아는 사람들의 정보를 담아주고 한명 한명씩 속해있는 파티를 조사해 준다.

- 조사할 때는 조사하지 않은 파티 중에서, 현재 사람이 속해있는 파티를 조사해 주었다.

- 만약 이미 진실을 알고 있는 사람을 발견하면 다시 그 사람을 확인하지 않아도 되므로  진실을 모르는 사람들의 정보를 큐에 담아주었다. 

- 현재 사람이 속해있는 파티가 존재했다면 해당 파티는 더 이상 과장되서 말할 수 없는 파티가 되므로 현재까지 과장되어 말할 수 있는 파티의 개수에서 1을 줄여준다.

 

🔹이미 진실을 아는 사람이거나, 이미 확인한 파티는 조사하지 않는다.

- 파티 방문 여부를 체크하는 Boolean배열과, 이미 진실을 알고 있는 사람 여부를 체크하는 Boolean배열을 사용해 주었다. 

 

코드

import java.util.*;
 
public class Main {
    
    static ArrayList<Integer> truth = new ArrayList<>();
    static ArrayList<Integer>[] party;
    static int n, m;
    static int total_party;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        m = scan.nextInt();
 
        int t = scan.nextInt();
        for(int i = 0; i < t; i++) {
            truth.add(scan.nextInt());
        }
 
        party = new ArrayList[m];
        for(int i = 0; i < m; i++) {
            party[i] = new ArrayList<>();
            
            int num = scan.nextInt();
            for(int j = 0; j < num; j++) {
                party[i].add(scan.nextInt());
            }
        }
 
        total_party = m;
        find_truth();
        System.out.println(total_party);
    }
 
    public static void find_truth() {
        Queue<Integer> q = new LinkedList<>();
        boolean[] party_visited = new boolean[m];
        boolean[] people_visited = new boolean[n + 1];
        for(int i = 0; i < truth.size(); i++) {
            q.offer(truth.get(i));
            people_visited[truth.get(i)] = true;
        }
 
        while(!q.isEmpty()) {
            int current  = q.poll();
 
            for(int i = 0; i < m; i++) {
                if(!party_visited[i] && party[i].contains(Integer.valueOf(current))) {
                    for(int j = 0; j < party[i].size(); j++) {
                        int next = party[i].get(j);
                        if(!people_visited[next]) {
                            people_visited[next] = true;
                            q.offer(next);
                        }
                    }
                    total_party--;
                    party_visited[i] = true;
                }
            }
        }
    }
}