[백준] 1043번 : 거짓말

문제

 

 

접근 방식

입력이 복잡하게 주어져서 이걸 어떻게 간선으로 표현할지 난감했는데

결국 진실을 아는 사람들과 연결된지만 확인하여

진실을 아는 사람, 그 사람들과 만난 적 있는 사람들이 참여한 파티라면

전체 파티 수에서 1씩 빼주면 된다.

 

우선 입력을 받을 때, 같은 파티에 참여한 사람들끼리 서로 인접 그래프에

동일하게 추가해준 후에, 진실을 아는 사람들만 시작 정점으로 하여

DFS로 탐색을 해주면서 방문한 모든 정점들을 참으로 바꿔주면

진실을 아는 사람과 만난 사람들이 누군지까지 알 수 있다.

 

그 후에 파티 참가자들을 확인하면서 진실을 아는지 확인해주면 된다.

 

 

풀이

public class Main {

	private static ArrayList<ArrayList<Integer>> near = new ArrayList<>();
	private static boolean[] isTrue;
	private static boolean[] isUsed;

	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());
		int s;
		int[] members;
		isTrue = new boolean[n + 1];
		isUsed = new boolean[n + 1];

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

		st = new StringTokenizer(br.readLine());

		int tr = Integer.parseInt(st.nextToken());
		int[] trs = new int[tr];
		ArrayList<int[]> parties = new ArrayList<>();

		for (int i = 0; i < tr; i++) {
			int people = Integer.parseInt(st.nextToken());
			trs[i] = people;
			isTrue[people] = true;
		}

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

			s = Integer.parseInt(st.nextToken());
			members = new int[s];

			for (int j = 0; j < s; j++) {
				members[j] = Integer.parseInt(st.nextToken());
			}

			parties.add(members);

			for (int j = 0; j < s; j++) {
				ArrayList<Integer> list = near.get(members[j]);

				for (int k = 0; k < s; k++) {
					if (j != k) list.add(members[k]);
				}
			}
		}

		for (int i = 0; i < tr; i++) {
			dfs(trs[i]);
		}

		for (int[] party : parties) {
			for (int member : party) {
				if (isTrue[member]) {
					m--;
					break;
				}
			}
		}

		System.out.println(m);
	}

	private static void dfs(int cur) {
		isUsed[cur] = true;
		isTrue[cur] = true;

		for (int next : near.get(cur)) {
			if (isUsed[next]) continue;
			dfs(next);
		}
	}
}