1. 관련 문제 🎯
문제 : 백준 1043 거짓말 😈
난이도 : 골드 4
2. 문제 소개 🧩
1️⃣ 파티에 갈 때마다, 지민이는 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다.
2️⃣ 지민이는 되도록이면 과장해서 이야기하려고 한다.
3️⃣ 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다.
따라서 지민이는 아래의 일을 모두 피해야 한다.
- 1) 이야기의 진실을 아는 몇몇 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기해야한다.
- 2) 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다.
4️⃣ 이야기의 진실을 아는 사람 N명이 주어진다.
5️⃣ 각 파티에 오는 사람들의 번호가 주어진다.
6️⃣ 지민이는 모든 파티에 참가해야 한다.
☝️ 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구해야 한다.
3. 문제 풀이 🖌️
- 위의 그림만 보면 각 파티별로 진실을 아는 사람의 번호가 있는지를 살펴보고, 진실을 아는 사람이 있는 파티에 참석한 사람의 경우 똑같이 진실을 아는 사람 된다고 생각할 수 있다!
그러면 왜 그래프 관련 문제일까?? 🤔
- 아래의 예시를 보면 알 수 있다!!
- 위에서 말한 대로 각 파티별로 진실을 아는 사람의 번호가 있는 경우 진실을 말하고, 없는 경우 진실을 말하지 않는다고 해보자~
그러면, 아래와 같은 경우 진실을 말하지 않는 파티는 총 3개가 된다.
그러나 정답은 바로 바로 3이 아닌 '2'임을 알 수 있다!!
따라서, 한 가지를 더 생각해줘야 한다🥲
- 각 파티는 위에서 아래로 순서대로 열리는 것이 아니므로, 진실을 아는 사람과 같은 파티에 참석한 사람은 어느 파티에서도 진실을 아는 사람이 된다.
- 따라서, 아래와 같이 처음부터 진실을 아는 사람인 1번과 같이 파티를 참석한 4번은 4번 단독으로 파티를 참가해도 진실만을 말해야 한다!!
위의 사진에서 오른쪽 그래프처럼 1번과 4번을 묶을 수 있다.
정리해보면
☝️ 각각의 파티를 보면서, 같이 파티를 한 사람을 하나의 그래프(그룹)로 묶는다.
✌️ 각각의 파티를 다시 한 번 살펴보면서, 해당 파티에 참석한 사람들 중에 진실을 아는 사람과 같은 그룹이 있는 경우 해당 파티는 진실을 말해야 한다.
3-1. 각각의 파티를 보면서, 같이 파티를 한 사람을 하나의 그래프로 묶는다.
☝️ 이때, Union-Find를 사용하여 같은 그룹으로 묶을 수 있다.
Union-Find 관련 내용은 https://velog.io/@da_na/2-3.-그리디-프로그래머스-섬-연결하기 를 참고하세요~!
int parent[51] = {0,};
vector<int> party[M]; //각 파티마다 오는 사람들의 번호
int find(int x){ //속한 그룹의 번호를 반환한다.
if(parent[x] == x){
return x;
}
return parent[x] = find(parent[x]);
}
void merge(int x, int y){ //같은 그룹으로 묶는다.
int X = find(x);
int Y = find(y);
if(X == Y) return;
parent[Y] = X;
}
for(int m=0; m<M; m++){
cin>>partyNums;
for(int i=0; i<partyNums; i++){
//파티에 참석한 사람들을 2번 살펴봐야 하므로 vector안에 저장해놓는다.
cin>>nums;
party[m].push_back(nums);
}
for(int i=0; i<partyNums-1; i++){
// 같은 파티에 참석한 사람들끼리 같은 그룹으로 묶는다.
int x = party[m][i];
int y = party[m][i+1];
merge(x,y);
}
}3-2. 각각의 파티를 다시 한 번 살펴보면서, 해당 파티에 참석한 사람들 중에 진실을 아는 사람과 같은 그룹이 있는 경우 해당 파티는 진실을 말해야 한다.
bool is_parent(int x, int y){ //같은 그룹인지를 살펴본다.
int X = find(x);
int Y = find(y);
if(X == Y) return true;
return false;
}
for(int i=0; i<M; i++){ //각각의 파티마다 진실을 아는 사람이 있는지 살펴본다.
bool check = false;
answer++;
for(int j=0; j<party[i].size(); j++){
for(int k=0; k<truthPeopleNums; k++){
//해당 파티에 진실을 아는 사람과 같은 그룹에 속한 사람이 있는 경우, 해당 파티는 진실을 말한다.
if(is_parent(parent[party[i][j]], parent[truthPeople[k]])){
answer--;
check = true;
break;
}
}
if(check == true){
break;
}
}
}4. 전체 코드 🔑
#include <iostream>
#include <vector>
using namespace std;
int parent[51] = {0,};
int find(int x){ //속한 그룹의 번호를 반환한다.
if(parent[x] == x){
return x;
}
return parent[x] = find(parent[x]);
}
void merge(int x, int y){ //같은 그룹으로 묶는다.
int X = find(x);
int Y = find(y);
if(X == Y) return;
parent[Y] = X;
}
bool is_parent(int x, int y){ //같은 그룹인지를 살펴본다.
int X = find(x);
int Y = find(y);
if(X == Y) return true;
return false;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N = 0, M = 0; //사람의 수, 파티의 수
cin >> N >> M;
int truthPeopleNums = 0; //이야기의 진실을 아는 사람의 수
vector<int> truthPeople; //이야기의 진실을 아는 사람들의 번호
vector<int> party[M]; //각 파티마다 오는 사람들의 번호
int nums;
cin >> truthPeopleNums;
for(int i=0; i<truthPeopleNums; i++){
cin>>nums;
truthPeople.push_back(nums);
}
int partyNums = 0; //각 파티마다 오는 사람의 수
int answer = 0;
for(int i=1; i<=N; i++){
parent[i] = i;
}
for(int m=0; m<M; m++){
cin>>partyNums;
for(int i=0; i<partyNums; i++){
cin>>nums;
party[m].push_back(nums);
}
for(int i=0; i<partyNums-1; i++){
int x = party[m][i];
int y = party[m][i+1];
merge(x,y);
}
}
for(int i=0; i<M; i++){ //각각의 파티마다 진실을 아는 사람이 있는지 살펴본다.
bool check = false;
answer++;
for(int j=0; j<party[i].size(); j++){
for(int k=0; k<truthPeopleNums; k++){
//해당 파티에 진실을 아는 사람과 같은 그룹에 속한 사람이 있는 경우, 해당 파티는 진실을 말한다.
if(is_parent(parent[party[i][j]], parent[truthPeople[k]])){
answer--;
check = true;
break;
}
}
if(check == true){
break;
}
}
}
cout<<answer<<"\n";
}5. 결과 🏆
컴퓨터공학과 학생이며, 백엔드 개발자입니다🐰