[BaekJoon] 1043 거짓말 (Java)

1.  문제 링크

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

2.  문제

요약

• 지민이는 파티에 갈 때마다 지민이가 가장 좋아하는 이야기를 하는데 그 이야기를 말할 때는 있는 그대로 진실로 말하거나 엄청나게 과장해서 말합니다.
• 되도록이면 과장해서 이야기하려고 하지만 거짓말쟁이로 알려지기 싫어합니다.
• 몇몇 사람들은 그 이야기의 진실을 알기 때문에 이런 사람들이 파티에 왔을 때는 지민이는 진실을 이야기할 수 밖에 없습니다.
• 지민이는 모든 파티에 참가해야 합니다.
• 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 50 이하의 자연수인 사람의 수 N과 파티의 수 M이 주어지고 두 번째 줄에 이야기의 진실을 아는 사람의 수와 번호가 주어지는데 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어집니다. 세 번째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 주어집니다.
  • 사람들의 번호는 1부터 N까지의 수로 주어집니다.
  • 진실을 아는 사람의 수는 0 이상 50 이하의 정수입니다.
  • 각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수입니다.
• 출력: 첫 번째 줄에 문제의 정답을 출력합니다.

3.  소스코드

BFS 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static HashMap<Integer, ArrayList<Integer>> personPerParty, partyPerPerson;
	static boolean[] people, parties;
	static int[] truthPeople;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		M = scanner.nextInt();
		people = new boolean[N + 1];
		parties = new boolean[M + 1];
		personPerParty = new HashMap<Integer, ArrayList<Integer>>();
		partyPerPerson = new HashMap<Integer, ArrayList<Integer>>();
		for(int person = 1; person <= N; person++) partyPerPerson.put(person, new ArrayList<>());
		for(int party = 1; party <= M; party++) personPerParty.put(party, new ArrayList<>());
		int num = scanner.nextInt();
		truthPeople = new int[num];
		for(int person = 0; person < num; person++) truthPeople[person] = scanner.nextInt();
		for(int party = 1; party <= M; party++) {
			int peopleNum = scanner.nextInt();
			for(int person = 0; person < peopleNum; person++) {
				int p = scanner.nextInt();
				partyPerPerson.get(p).add(party);
				personPerParty.get(party).add(p);
			}
		}
	}
	
	static void solution() {
		for(int person : truthPeople) bfs(person);
		int result = 0;
		for(int party = 1; party <= M; party++) {
			if(!parties[party]) result++;
		}
		System.out.println(result);
	}
	static void bfs(int start) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(start);
		people[start] = true;
		while(!queue.isEmpty()) {
			int cur = queue.poll();
			for(int party : partyPerPerson.get(cur)) {
				parties[party] = true;
				for(int person : personPerParty.get(party)) {
					if(!people[person]) {
						people[person] = true;
						queue.add(person);
					}
				}
			}
		}
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

분리 집합 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static int[] parents, truthPeople;
	static HashMap<Integer, ArrayList<Integer>> peoplePerParty;
	static boolean[] people;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		M = scanner.nextInt();
		parents = new int[N + 1];
		for(int person = 1; person <= N; person++) parents[person] = person;
		peoplePerParty = new HashMap<>();
		for(int party = 1; party <= M; party++) peoplePerParty.put(party, new ArrayList<>());
		people = new boolean[N + 1];
		int num = scanner.nextInt();
		truthPeople = new int[num];
		for(int person = 0; person < num; person++) truthPeople[person] = scanner.nextInt();
		for(int party = 1; party <= M; party++) {
			int peopleNum = scanner.nextInt();
			if(peopleNum == 1) {
				peoplePerParty.get(party).add(scanner.nextInt());
				continue;
			}
			int first = scanner.nextInt();
			peoplePerParty.get(party).add(first);
			for(int person = 1; person < peopleNum; person++) {				
				int cur = scanner.nextInt();
				union(first, cur);
				peoplePerParty.get(party).add(cur);
			}
		}
	}
	
	static void solution() {
		for(int person : truthPeople) {
			if(!people[person]) {
				int parent = findParents(person);
				people[person] = true;
				for(int p = 1; p <= N; p++) {
					if(parent == findParents(p)) people[p] = true;
				}
			}
		}
		int result = 0;
		for(int party : peoplePerParty.keySet()) {
			boolean flag = false;
			for(int person : peoplePerParty.get(party)) {
				if(people[person]) {
					flag = true;
					break;
				}
			}
			if(!flag) result++;
		}
		System.out.println(result);
	}
	
	static int findParents(int person) {
		if(person == parents[person]) return person;
		return parents[person] = findParents(parents[person]);
	}
	
	static void union(int person1, int person2) {
		int parent1 = findParents(person1);
		int parent2 = findParents(person2);
		if(parent1 != parent2) {
			if(parent1 < parent2) parents[parent2] = parent1;
			else parents[parent1] = parent2;
		}
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}