1043번 : 거짓말

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

1043번: 거짓말

 

문제

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.

사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.

둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.

셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.

N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수는 0 이상 50 이하의 정수, 각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수이다.

 

출력

첫째 줄에 문제의 정답을 출력한다.

 

---

소스코드

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

public class Main {
    static ArrayList<ArrayList<Integer>> inputList = new ArrayList<>();
    static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    static boolean[] flags, visited;
    static int n, m;

    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());
        flags = new boolean[n + 1];

        st = new StringTokenizer(br.readLine(), " ");
        int c = Integer.parseInt(st.nextToken());

        for (int i = 0; i < c; i++) {
            int parseInt = Integer.parseInt(st.nextToken());
            flags[parseInt] = true;
        }

        for (int i = 0; i < m; i++) {
            inputList.add(new ArrayList<>());
        }
        
        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }

        // 입력값 inputList애 저장
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int parseInt = Integer.parseInt(st.nextToken());
            for (int j = 0; j < parseInt; j++) {
                inputList.get(i).add(Integer.parseInt(st.nextToken()));
            }
        }

        // 그래프 연결
        for (int i = 0; i < m; i++) {
            int pre = inputList.get(i).get(0);
            for (int j = 1; j < inputList.get(i).size(); j++) {
                list.get(pre).add(inputList.get(i).get(j));
                list.get(inputList.get(i).get(j)).add(pre);
                pre = inputList.get(i).get(j);
            }
        }

        // 파티 구하기
        int result = 0;
        for (int i = 0; i < m; i++) {
            Integer v = inputList.get(i).get(0);
            visited = new boolean[n + 1];
            if(bfs(v) == false) {
                result += 1;
            }
        }

        System.out.println(result);
    }

    static boolean bfs(int x) {
        Deque<Integer> deque = new ArrayDeque<>();
        deque.addLast(x);
        boolean flag = false;

        if(flags[x]) return true;
        while(!deque.isEmpty()) {
            Integer now = deque.pollFirst();
            for (int i = 0; i < list.get(now).size(); i++) {
                Integer nx = list.get(now).get(i);
                if(flags[nx]) {
                    flag = true;
                    break;
                }
                if(!visited[nx]) {
                    visited[nx] = true;
                    deque.addLast(nx);
                }
            }
            if(flag) break;
        }

        return flag;
    }
}

 

해결방법

입력값을 어딘가 저장을 해놔야 문제를 풀 수 있을 것 같아서 inputList에 각 파티마다 오는 사람의 번호를 입력해두었다.

이후 inputList를 이용해 그래프를 연결해 주었다. 

 

만약 입력값이 아래와 같다면

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

 

아래처럼 그래프는 형성이 된다.

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

 

그래프가 형성됐다면 과장을 할 수 있는 파티 개수를 구할 수 있다.

각 파티에 오는 사람들의 번호가 입력된 inputList를 이용해 각 파티마다 bfs 탐색을 해주었다. 

탐색 도중 과장을 할 수 없는 사람의 번호가 있다면 true, 없다면 false를 반환하였다.

 

과장을 할 수 없는 사람의 번호는 입력값을 받아 flags[]에 입력해 두었기에 이를 보고 판단할 수 있다.