백준: 1043번 (거짓말) [JAVA]

문제 링크

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

1043번: 거짓말

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어지는 진실을 아는 사람과, 파티 참가인원 정보를 바탕으로 진실을 아는 사람이 참가하는 파티, 파티에 대한 참가자들로 구성된 인접리스트 초기화
2. 이후 진실을 아는 사람들을 시작으로 dfs 탐색을 진행
3. 전체 파티 중에서 방문한 적이 없는 파티들의 개수를 반환

 문제에서 원하는 답인 과장된 이야기를 할 수 있는 파티의 개수를 구하려면, 진실된 이야기를 아는 사람들이 참가하는 파티를 시작으로 그 속에 참가한 인원들이 참가하는 파티를 계속 체크하는 dfs 탐색이 필요하다.

 결국 문제 자체 해결을 위한 알고리즘은 dfs 하나로 간단하지만 이 탐색을 위해 필요한 자료구조를 만들어야 한다.  전체적인 dfs 과정이 진실을 아는 사람이 참가한 파티 체크 -> 해당 파티 속 사람들이 참가하는 다른 파티 체크의 반복이기 때문에, 파티 속 참가자들의 집합과 특정 사람들이 참가하는 파티들의 집합을 모두 자료구조로 만들어야 한다.

 우선 진실을 아는 사람들이 주어지는 입력을 따로 집합으로 저장 후, 이후 주어지는 파티 - 참가자들 정보들을 가지고 2개의 자료구조를 구축한 다음 dfs 탐색을 진행한다. 이후 전체 파티를 돌며 방문 체크가 되지 않은 파티들의 개수를 반환하면 된다.

 

public class Main {
    static ArrayList<Integer>[] parties, participantsIn;
    static int[] knownPeople;
    static boolean[] canLie;

    public static void main(String[] args) throws IOException{
        int answer = 0;
        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());

        parties = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            parties[i] = new ArrayList<>();
        }
        participantsIn = new ArrayList[M];
        for (int i = 0; i < M; i++) {
            participantsIn[i] = new ArrayList<>();
        }
        canLie = new boolean[M];

        //진실을 아는 사람 저장
        st = new StringTokenizer(br.readLine());
        int knownPeopleNum = Integer.parseInt(st.nextToken());
        knownPeople = new int[knownPeopleNum];

        for (int i = 0; i < knownPeopleNum; i++) {
            knownPeople[i] = Integer.parseInt(st.nextToken());
        }
        
        //파티-참가자, 참가자-파티 저장
        for (int party = 0; party < M; party++) {
            st = new StringTokenizer(br.readLine());
            int peopleNum = Integer.parseInt(st.nextToken());

            for (int j = 0; j < peopleNum; j++) {
                int person = Integer.parseInt(st.nextToken());

                parties[person].add(party);
                participantsIn[party].add(person);
            }
        }

        //dfs
        for (int i = 0; i < knownPeople.length; i++) {
            dfs(knownPeople[i]);
        }

        for (int i = 0; i < canLie.length; i++) {
            if (!canLie[i]) {
                ++answer;
            }
        }

        System.out.println(answer);
    }

    static void dfs(int person) {//dfs 기반 탐색
        for (int i = 0; i < parties[person].size(); i++) {
            int party = parties[person].get(i);

            if (!canLie[party]) {
                canLie[party] = true;

                for (int j = 0; j < participantsIn[party].size(); j++) {
                    int nextPerson = participantsIn[party].get(j);
                    dfs(nextPerson);
                }
            }
        }
    }
}

결과