BOJ 1043
위 문제는 백준 사이트의 알고리즘 1043 문제에 관한 설명입니다.
문제
지민이는 파티에 가서 이야기 하는 것을 좋아한다.
파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다.
지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다.
당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다.
하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다.
따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다.
당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다.
지민이는 이런 일을 모두 피해야 한다.
사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다.
그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다.
이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.
입력
째 줄에 사람의 수 N과 파티의 수 M이 주어진다.
둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다.
진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.
셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.
N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수와 각 파티마다 오는 사람의 수는 모두 0 이상 50 이하의 정수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Lie{
static int N, M, K;//사람의 수 N과 파티의 수 M, 이야기의 진실을 아는 사람의 수
static int count;//과장된 이야기를 할 수 있는 파티 수
static ArrayList<Integer> party[];
static ArrayList<Integer> people[];
static ArrayList<Integer> know;
static boolean visited[];
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
K = Integer.parseInt(st.nextToken());
people = new ArrayList[N+1];
for(int i = 0 ; i < N+1;i++)
{
people[i] = new ArrayList<>();
}
party = new ArrayList[M+1];
for(int i = 0 ; i < M+1;i++)
{
party[i] = new ArrayList<>();
}
know = new ArrayList<>();
visited = new boolean[M+1];
for(int i = 0 ; i < K; i++)
{
know.add(Integer.parseInt(st.nextToken()));
}
for(int i = 0; i < M; i++){
st = new StringTokenizer(br.readLine());
int num = Integer.parseInt(st.nextToken());
for(int j = 0 ; j < num; j++)
{
int value = Integer.parseInt(st.nextToken());
party[i].add(value); //party의 arraylist에 사람의 번호 추가
people[value].add(i);//사람의 arraylist에 파티의 번호 추가 = 이렇게 하면 서로가 그래프로 연결된 노드들 처럼 그려짐
}
}
bfs();
System.out.println(count);
}
public static void bfs(){
Queue<Integer> queue= new LinkedList<Integer>();
for(int i = 0 ; i < know.size();i++)//진실을 아는 사람의 수만큼
{
for(int j=0; j < people[know.get(i)].size();j++)//진신을 아는 사람의 번호 만큼
{
if(!visited[people[know.get(i)].get(j)])//방문한 적이 없다면?(거짓말을 해도 상관없다면)
{ visited[people[know.get(i)].get(j)]=true;
queue.add(people[know.get(i)].get(j));// queue에 추가
}
}
}
while(!queue.isEmpty()){
int value = queue.poll();
for(int i = 0; i < party[value].size();i++)//진실을 알고있는 사람이 참여한 파티가 들어있는값을 value에 넣음
{ //그 파티에 속한 사람들도 진실을 알아야하므로 연결된 사람들을 체크함
for(int j=0; j < people[party[value].get(i)].size();j++)//사람들의 arrsylist번호에 몇번쨰 파티인지
{
if(!visited[people[party[value].get(i)].get(j)])
{ //해당 값에 방문한 적이 없다면 거짓말을 해도된다면
visited[people[party[value].get(i)].get(j)] = true;// true
queue.add(people[party[value].get(i)].get(j));
}
}
}
}
for(int i = 0 ; i < M;i++)
{
if(!visited[i]){
count++;
}
}
}
}
문제 이해도 어렵고.. 푸는 과정도 어려웠습니다.
주석을 달아놨으니 이해하기 쉬웠으면 합니다.