[JAVA] 1043 거짓말

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

1043번: 거짓말

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class bj1043 {
    static int N;
    static int M;
    static ArrayList<Integer> original; //맨 처음에 진실을 알고 있던 사람들
    static ArrayList<Integer> people;
    static List<ArrayList<Integer>> partyman;//파티에 참석한 인원들
    static ArrayList<Integer> truthman; // 막판에 진실을 알고 있는 사람들
    static int count;
    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());
        count = M;
        st = new StringTokenizer(br.readLine());
        int len = Integer.parseInt(st.nextToken());
        original = new ArrayList<>();
        if(len>0){ //진실을 알고 있는 사람의 수가 0보다 크면 original에 진실을 아는 애들을 추가해준다.
            for(int i=0;i<len;i++){
                original.add(Integer.parseInt(st.nextToken()));
            }
        }else{
            //진실을 알고 있는 사람의 수가 0명일 경우 파티 개수인 M을 return
            System.out.println(count);
            return;
        }
        partyman = new ArrayList<>();
 
        //파티 순서별로 파티에 참석하는 사람들 리스트를 넣어주는 과정
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            len = Integer.parseInt(st.nextToken());
            people = new ArrayList<>();
            for(int j=0;j<len;j++){
                people.add(Integer.parseInt(st.nextToken()));
            }
            partyman.add(people);
        }
 
        truthman = new ArrayList<>();
 
        //맨 처음에 진실을 아는 사람들을 추가했던 리스트인 original이 빌 때 까지 반복문을 돌린다.
        while(!original.isEmpty()){
            int person = original.get(0); //첫번째 사람을 뽑아서,
            original.remove(0); //뽑았으면 original에서 지우고 (Queue에 pop을 표현하고 싶었음)
            truthman.add(person); //찐으로 진실을 아는 사람 리스트에 추가한다.
            for(int j=0;j<M;j++){ //파티 리스트를 돌면서
                if(partyman.get(j).contains(person)){ //파티 j에 진실을 아는 사람이 포함되어 있는지를 확인하고 있으면
                    for(int k=0;k<partyman.get(j).size();k++){ //파티 j를 모두 돌면서
                        Integer target = partyman.get(j).get(k); 
                        if(!(original.contains(target)) && !(truthman.contains(target))){ //진실을 아는 사람이 포함된 리스트인 original, truthman에 없으면
                            original.add(target); //original에 추가함.
                        }
                    }
                }
            }
        }
/*
original이라는 리스트는 계속 원소가 추가되고 pop되면서 해당 원소가 파티 리스트에 존재하는지를 따져야 하고,
pop된 애들 (한번이라도 진실을 아는 애랑 있었던 애들)을 저장할 곳이 필요해서 truthman이라는 리스트를 만들었다.
original에서 팝된 원소들은 모두 truthman이라는 리스트에 저장된다.
 
original, 즉 진실을 아는 애들 리스트의 원소가 아무도 없을 때까지 반복한 후 
*/
 
 
        for(int i=0;i<M;i++){
            for(int j=0;j<truthman.size();j++){ //파티를 돌면서 truthman이 하나라도 포함된 파티가 있으면 파티 개수에서 -1을 하고 다음 파티로 넘어감.
                if (partyman.get(i).contains(truthman.get(j))){
                    count -=1;
                    break;
                }
            }
        }
        
        System.out.println(count); //마지막까지 살아남는 파티 개수가 거짓말을 해도 되는 파티 개수! 
    }
}

[풀이]

주석으로 달았음.

 

아직 함수 재정의하는게 어려워서 Deque나 Queue를 쓰려고 했는데  contains함수 재정의를 하려니 어려워서 그냥 Arraylist로 풀었다.

다섯달전에도 비슷한 로직으로 풀었는데 코드 길이 차이가 재밌네...