문제
지민이는 파티에서 과장된 이야기를 한다. 진실을 아는 사람이 파티에 참가하면 거짓말을 할 수 없다. 같은 파티에 참가한 사람들은 서로 진실을 공유한다. 지민이가 거짓말을 할 수 있는 파티의 최대 수를 구한다.
입력
- 첫째 줄: 사람의 수 N과 파티의 수 M
- 둘째 줄: 진실을 아는 사람의 수와 그 사람들의 번호
- 이후 M줄: 각 파티의 참가 인원 수와 참가자 번호
출력
지민이가 거짓말을 할 수 있는 파티의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 3 1 1 2 1 2 1 3 3 2 3 4 | 1 |
풀이
같은 파티에 참가한 사람들을 Union-Find로 같은 집합으로 묶는다. 진실을 아는 사람들의 대표 집합을 기준으로, 각 파티 참가자 중 하나라도 진실 그룹과 같은 집합이면 해당 파티에서 거짓말을 할 수 없다.
- N+1 크기의
p배열로 Union-Find를 초기화한다. - 진실을 아는 첫 번째 사람을 대표 P로 정하고, 나머지 진실 아는 사람들의 부모를 P로 설정한다.
- 각 파티의 참가자들을 모두 Union하여 같은 집합으로 묶는다.
- 각 파티의 첫 번째 참가자의 집합이 진실 그룹과 동일하면 거짓말 불가 파티로 처리한다.
- 전체 파티 수 M에서 거짓말 불가 파티 수를 빼서 출력한다.
핵심 아이디어: 같은 파티 참가자끼리는 진실 전파가 되므로 Union-Find로 같은 집합에 묶는다. 진실을 아는 사람이 한 명이라도 포함된 집합은 진실 그룹이 된다. 경로 압축(path compression)을 사용한 findSet으로 집합 조회를 효율화한다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Day94BOJ1043거짓말서로소집합 { // 1043 거짓말
static int N, M, T, P, ans;
static int[] p;
static List<Integer>[] prt;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 사람 수
M = Integer.parseInt(st.nextToken()); // 파티 수
ans = M;
p = new int[N + 1];
prt = new ArrayList[M];
makeSet();
// 진실을 아는 사람 수, 번호
st = new StringTokenizer(br.readLine());
T = Integer.parseInt(st.nextToken()); // 진실을 아는 사람 수
if (st.hasMoreTokens())
P = Integer.parseInt(st.nextToken()); // 진실그룹 아무나 대표정하기
while (st.hasMoreTokens())
p[Integer.parseInt(st.nextToken())] = P;
for (int i = 0; i < M; i++) {
prt[i] = new ArrayList<>();
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()); // 이번 파티 참석인원
int t = Integer.parseInt(st.nextToken());
prt[i].add(t);
for (int j = 1; j < n; j++) {
int s = Integer.parseInt(st.nextToken());
prt[i].add(s);
unionSet(t, s);
}
}
for (int i = 0; i < M; i++)
if (findSet(P) == findSet(prt[i].get(0)))
ans--;
System.out.println(ans);
br.close();
}
private static void makeSet() {
for (int i = 0; i < N + 1; i++)
p[i] = i;
}
private static int findSet(int n) {
return p[n] = (n == p[n]) ? n : findSet(p[n]);
}
private static boolean unionSet(int a, int b) { // 안써도 될듯.
if ((a = findSet(a)) == (b = findSet(b)))
return false;
p[b] = a;
return true;
}
}복잡도
- 시간: O((N + M) * alpha(N)) — Union-Find 연산은 거의 O(1), alpha는 역 아커만 함수
- 공간: O(N + M) — 분리 집합 배열 및 파티 참가자 리스트