지민이는 파티에 갈 때마다 자기가 가장 좋아하는 이야기를 한다. 이야기는 과장할수록 더 재미있어지므로 되도록이면 과장해 이야기하려 한다. 문제는 몇몇 사람들이 그 이야기의 진실을 안다는 것이다. 지민이는 이야기를 과장한게 들켜서 거짓말쟁이가 되는 건 싫어한다. 그래서 이 사람들이 파티에 왔을 때는 진실을 이야기할 수밖에 없다.
사람의 수 N이 주어지고, 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때 지민이가 거짓말쟁이로 알려지지 않으면서 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.
(시간 제한 2초)
입력
1번재 줄에 사람의 수 N과 파티의 수 M이 주어진다. 2번째 줄에 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고, 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다. 3번째 줄에서 M개의 줄에는 각 파티마다 오는 사람들의 수와 번호가 같은 방식으로 주어진다. N, M은 50 이하의 자연수, 진실을 아는 사람의 수와 각 파티마다 오는 사람의 수는 모두 0 이상 50 이하의 정수다.
출력
1번째 줄에 문제의 정답을 출력한다.
예제 입력
8 5 // 사람 수, 파티 수
3 1 2 7 // 진실을 아는 사람 정보
2 3 4 // 파티 정보
1 5
2 5 6
2 6 8
1 8
예제 출력
5
1단계 - 문제 분석하기
이 문제의 핵심은 파티에 참여한 사람들을 1개의 집합으로 생각하고, 각각의 파티마다 union 연산을 이용해 사람들을 연결하는 것이다. 이 작업을 하면 1개의 파티에 있는 모든 사람들은 같은 대표 노드를 바라보게 된다. 이후 각 파티의 대표 노드와 진실을 알고 있는 사람들의 각 대표 노드가 동일한지 find 연산을 이용해 확인함으로써 과장된 이야기를 할 수 있는지 판단할 수 있다.
2단계 - 손으로 풀어 보기
1 진실을 아는 사람 데이터, 파티 데이터, 유니온 파인드를 위한 대표 노드 자료구조를 초기화한다.
2 각 파티 정보마다 union 연산을 수행해 각 파티에 참여한 사람들을 1개의 그룹으로 만든다.
3 find 연산을 수행해 각 파티의 대표 노드와 진실을 아는 사람들이 같은 그룹에 있는지 확인한다. 파티 사람 노드는 모두 연결돼 있으므로 아무 사람이나 지정해 find 연산을 수행하면 된다. 파티의 대표 노드가 진실을 아는 사람들과 다른 그룹에 있다면 결과값을 증가시킨다.
4 결과값을 출력한다.
3단계 - sudo코드 작성하기
N(사람 수) M(파티 수)
T(진실을 아는 사람 수) trueP(진실을 아는 사람 데이터) party(파티 데이터)
parent(대표 노드 저장 배열)
for(N만큼 반복)
{
대표 노드랄 자기 자신으로 초기화
}
for(i -> M만큼 반복)
{
firstPeople(i번째 파티의 1번째 사람)
for(j -> i번째 파티의 사람 수만큼 반복)
{
union(firstPeople, j)
}
}
for(i -> M만큼 반복하기)
{
firstPeople(i번째 파티의 1번째 사람)
for(j -> 진실을 아는 사람들의 수만큼 반복)
{
find(firstPeople), find(trueP[j]) 비교하기
} 모두 다른 경우 결과값 1 증가
}
결과값 출력하기
union(a, b) {
a와 b의 대표 노드 찾기
두 원소의 대표 노드끼리 연결하기
}
find(a) {
a가 대표 노드면 리턴
아니면 a의 대표 노드값을 find(parent[a])값으로 저장.
}4단계 - 코드 구현하기
import java.util.ArrayList;
import java.util.Scanner;
public class Q52 {
public static int[] parent;
public static int[] trueP;
public static ArrayList<Integer>[] party;
public static int result;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int T = sc.nextInt();
result = 0;
parent = new int[N+1];
for(int i = 1; i < N+1; i++){
parent[i] = i;
}
trueP = new int[T];
for(int i = 0; i < T; i++){
trueP[i] = sc.nextInt();
}
party = new ArrayList[M];
for(int i = 0; i < M; i++){
party[i] = new ArrayList<Integer>();
int num = sc.nextInt();
for(int j = 0; j < num; j++){
party[i].add(sc.nextInt());
}
}
for(int i = 0; i < M; i++){
int firstPeople = party[i].get(0);
for(int j = 1; j < party[i].size(); j++){
union(firstPeople, party[i].get(j));
}
}
for(int i = 0; i < M; i++){
int firstPeople = party[i].get(0);
boolean isPossible = true;
for(int j = 0; j < trueP.length; j++){
if(find(firstPeople) == find(trueP[j])){
isPossible = false;
break;
}
}
if(isPossible == true)
result += 1;
}
System.out.println(result);
}
public static void union(int a, int b){
a = find(a);
b = find(b);
if(a != b){
parent[b] = a;
}
}
public static int find(int a){
if(a == parent[a])
return a;
else
return parent[a] = find(parent[a]);
}
}
- Do it! 알고리즘 코딩테스트 자바 편
