문제 설명
- 입력 정보:
- 첫 줄에 사람 수 n과 파티 수 m이 주어집니다.
- 두 번째 줄에 진실을 아는 사람들의 수와 번호가 주어집니다.
- 그 다음 m개의 줄에는 각 파티에 참석하는 사람들의 번호가 주어집니다.
- 조건:
- 각 파티에 진실을 아는 사람이 포함되면 그 파티에서는 거짓말을 할 수 없습니다.
- 진실을 아는 사람과 연결된 사람들도 모두 진실을 알게 됩니다 (진실을 아는 사람과 같은 파티에 참석한 경우 간접적으로 진실을 알게 되는 경우).
- 목표:
- 가능한 많은 파티에서 거짓말을 할 수 있도록 하려면, 진실을 아는 사람들과 연결된 파티는 모두 제외하고 최대한 많은 파티에서 거짓말을 할 수 있도록 합니다.
접근 방법
이 문제를 해결하기 위해서는 진실을 아는 사람들과 연결된 모든 파티와 사람들을 탐색하고, 이 파티들을 제외한 나머지 파티에서 거짓말을 할 수 있는지 판단해야 합니다.
- BFS/DFS를 이용한 연결 관계 탐색:
- 모든 파티와 참가자들을 연결된 그래프로 보고, 진실을 아는 사람과 연결된 모든 사람과 파티를 탐색합니다.
- 탐색된 파티는 거짓말을 할 수 없는 파티로 설정합니다.
- 집합(Set)과 리스트(List)를 이용하여 구현:
- truePeople 집합(Set)을 통해 진실을 아는 사람을 관리합니다.
- 각 파티에 참여하는 사람들을 리스트로 저장하고, 이 리스트를 탐색하면서 연결 관계를 파악합니다.
import java.io.*;
import java.util.*;
public class Boj1043 {
static int n, m;
static Set<Integer> truePeople = new HashSet<>(); // 진실을 아는 사람
static List<List<Integer>> party = new ArrayList<>();
static boolean[] partyRestricted; // 거짓말을 할 수 없는 파티
static List<List<Integer>> partiesOfPeople = new ArrayList<>(); // 각 사람별로 참석한 파티 목록
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
n = Integer.parseInt(input[0]); // 사람 수
m = Integer.parseInt(input[1]); // 파티 수
String[] trues = br.readLine().split(" ");
int trueNumber = Integer.parseInt(trues[0]); // 진실을 아는 사람 수
for (int i = 1; i <= trueNumber; i++) {
truePeople.add(Integer.parseInt(trues[i]));
}
// 초기화
for (int i = 0; i <= n; i++) {
partiesOfPeople.add(new ArrayList<>());
}
partyRestricted = new boolean[m];
// 파티 정보 입력 및 사람과 파티 관계 매핑
for (int i = 0; i < m; i++) {
String[] str = br.readLine().split(" ");
int partySize = Integer.parseInt(str[0]);
List<Integer> currentParty = new ArrayList<>();
for (int j = 1; j <= partySize; j++) {
int person = Integer.parseInt(str[j]);
currentParty.add(person);
partiesOfPeople.get(person).add(i); // 사람별 참석 파티 등록 => 해당 person이 참석한 파티 번호
}
party.add(currentParty);
}
// BFS를 사용하여 진실을 전파하는 과정
Queue<Integer> queue = new LinkedList<>(truePeople); // 진실을 아는 사람들로 구성
while (!queue.isEmpty()) {
int person = queue.poll();
for (int p : partiesOfPeople.get(person)) { // 진실을 아는 사람들이 존재하는 파티
if (!partyRestricted[p]) {
partyRestricted[p] = true; // 해당 파티는 거짓말을 할 수 없음
for (int participant : party.get(p)) {
if (!truePeople.contains(participant)) {
truePeople.add(participant);
queue.add(participant); // 새로운 사람을 진실을 아는 사람에 추가
}
}
}
}
}
// 거짓말할 수 있는 파티 개수 계산
int answer = 0;
for (int i = 0; i < m; i++) {
if (!partyRestricted[i]) {
answer++;
}
}
System.out.println(answer);
}
}코드 설명
- 입력 처리:
- truePeople 집합을 통해 진실을 아는 사람을 저장합니다.
- 각 파티에 참석한 사람 목록을 party 리스트에 저장합니다.
- peopleInParty 리스트는 각 사람별로 참석한 파티의 번호를 저장합니다.
- BFS로 진실 전파:
- truePeople 집합의 사람들을 시작점으로 BFS를 수행하여, 진실을 아는 사람과 연결된 모든 파티와 사람들을 찾습니다.
- partyRestricted 배열을 사용하여 거짓말을 할 수 없는 파티를 표시합니다.
- 거짓말할 수 있는 파티 개수 계산:
- 모든 파티를 순회하면서 partyRestricted 배열에서 false인 파티 개수를 세어 출력합니다.
Q. 파티를 참석하는 순서는 고려하지 않아도 되는가??
이 문제의 핵심은 진실을 아는 사람과 연결된 모든 사람과 파티를 찾아내는 것이지, 특정 파티를 먼저 탐색하는 순서에 의해 결과가 달라지는 것은 아닙니다.
- 진실을 전파하는 과정은 연결된 컴포넌트를 찾는 과정:
- 이 문제는 그래프 탐색 문제로 볼 수 있습니다. 진실을 아는 사람을 시작으로 같은 파티에 참여한 사람들로 진실이 전파됩니다.
- 마치 그래프에서 연결된 컴포넌트를 BFS나 DFS를 통해 탐색하는 것처럼, 진실이 전파되는 모든 사람과 파티를 한 번에 찾는 것이 중요합니다.
- 파티를 탐색하는 순서는 달라도, 최종적으로 진실을 아는 사람들로 연결된 모든 컴포넌트가 탐색되기 때문에 결과가 동일합니다.
- 모든 파티를 방문하는 방식:
- 어떤 파티를 먼저 탐색하든, 결국 진실을 아는 사람과 연결된 모든 파티를 방문하게 됩니다.
- 따라서 진실을 아는 사람과 연결된 사람들은 모두 진실을 아는 상태가 되어, 그 사람들로 구성된 파티는 모두 거짓말을 할 수 없는 상태가 됩니다.
- BFS나 DFS 모두 각 파티에 한 번씩만 방문하며, 진실을 아는 사람과 연결된 파티들을 모두 탐색하기 때문에 순서가 상관없습니다.
- 결과 계산은 탐색 완료 후 이루어짐
- 모든 탐색이 끝난 후에야 비로소 partyRestricted 배열을 이용해 거짓말이 가능한 파티를 세게 됩니다.
- 즉, 탐색 중간에 어떤 파티를 먼저 방문하더라도 최종 결과에는 영향을 주지 않습니다.
예시를 통해 이해하기
예를 들어, 다음과 같은 상황을 생각해봅시다:
- 진실을 아는 사람: {1}
파티 구성
- 파티 1: {1, 2}
- 파티 2: {2, 3}
- 파티 3: {3, 4}
- 파티 4: {5, 6}
진실을 아는 사람 1을 시작으로 파티를 탐색하면 다음과 같은 전파가 일어납니다:
- 파티 1에서 1이 2에게 진실을 전파.
- 파티 2에서 2가 3에게 진실을 전파.
- 파티 3에서 3이 4에게 진실을 전파.
따라서, 파티 1, 2, 3은 모두 거짓말을 할 수 없습니다. 파티 4는 진실을 아는 사람과 연결되어 있지 않으므로 거짓말을 할 수 있습니다.
어떤 파티를 먼저 방문하든, 결과는 동일하게 됩니다.
결론
탐색 순서가 중요한 문제는 아니며, 모든 연결된 파티를 탐색하는 것이 중요합니다. BFS든 DFS든 모두 연결된 컴포넌트를 한 번에 탐색하기 때문에, 탐색 순서에 관계없이 최종 결과는 동일합니다.
꾸준함으로 성장하기