일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- BFS
- 브루트포스
- 에러
- 분할정복
- 파이어베이스
- 맵
- 자료 구조
- 코드트리조별과제
- 코드트리 조별과제
- 코딩테스트
- 멀티맵
- 코드트리
- c++풀이
- dfs
- 백트래킹
- 문자열
- 그래프
- c++
- dp
- 파이어스토어
- 코틀린
- 안드로이드
- 그래프 이론
- 다이나믹 프로그래밍
- 풀이
- 시뮬레이션
- 다익스트라
- 그래프 탐색
- map
- 백준
- Today
- Total
Kangho_Story
[백준] 1043번 거짓말 C++ 풀이 본문
알고리즘 분류
- 자료구조
- 그래프 이론
- 그래프 탐색
- 분리 집합
문제 설명
지민이는 파티에 가서 이야기하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또 다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.
사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.
둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.
셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.
N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수는 0 이상 50 이하의 정수, 각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수이다.
출력 설명
첫째 줄에 문제의 정답을 출력한다.
예제 입력
4 3
0
2 1 2
1 3
3 2 3 4
4 1
1 1
4 1 2 3 4
4 1
0
4 1 2 3 4
4 5
1 1
1 1
1 2
1 3
1 4
2 4 1
10 9
4 1 2 3 4
2 1 5
2 2 6
1 7
1 8
2 7 8
1 9
1 10
2 3 10
1 4
8 5
3 1 2 7
2 3 4
1 5
2 5 6
2 6 8
1 8
3 4
1 3
1 1
1 2
2 1 2
3 1 2 3
예제 출력
3
0
1
2
4
5
0
아이디어
처음에는 2차원 배열을 선언하고 각 집합별로 진실을 말한 번호를 T로 놓고 거짓을 말한 번호는 F로 놓고 다음 집합이 이전 집합의 T를 계승하는 방식으로 가려고 했다. 하지만 이렇게 하면 F에서T로 변한 경우 연속적인 계승이 어렵다는 한계가 있었다. 그래서 map을 사용해서 진실 집합과 거짓 집합을 만든 후 거짓 집합은 map을 담을 수 있는 vector에 차례로 넣고
진실 번호는 모두 진실 집합 1개에 합쳤다.
이후 거짓 집합에 있는 번호 중 진실 집합에 있는 번호가 존재한다면 해당 거짓 집합을 전부 진실 집합으로 옮기고 해당 거짓 집합은 제거한다.
이후 옮긴 번호를 재귀적으로 남은 거짓 집합 중에서 비교하는 방식으로 탐색을 진행하고 남은 거짓 집합의 개수를 출력한다.
알고리즘
거짓 집합에 있는 숫자 중에 진실 집합에 있는 숫자와 동일한 숫자가 있다면
해당 집합을 모두 진실 집합으로 이동시키고 이동시킨 숫자 중 거짓 집합에 속하는 숫자가 있는지 재귀적으로 탐색한다.
탐색이 종료되면 남아있는 거짓 집합의 개수를 출력한다.
코드
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int n,m,tn,cnt=0;
vector<map<int,bool>> Falsepp;
map<int,bool> Truepp;
void relay(int a)
{
for(auto &b : Falsepp)
{
if(b.find(a) != b.end())
{
Truepp.insert(b.begin(), b.end());
map<int,bool> tempvec = b;
map<int,bool> clearmap;
b = clearmap;
for(auto &c : tempvec) relay(c.first);
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>tn;
for(int i=0,temp; i<tn; i++)
{
cin>>temp;
Truepp.insert({temp,true});
}
for(int i=0,find,r; i<m; i++)
{
cin>>r;
map<int,bool> tempmap;
find=0;
for(int j=0,temp; j<r; j++)
{
cin>>temp;
tempmap.insert({temp,false});
if(Truepp.find(temp) != Truepp.end()) find=1;
}
if(find==1) Truepp.insert(tempmap.begin(), tempmap.end());
else Falsepp.push_back(tempmap);
}
for(auto &a : Truepp) relay(a.first);
for(int i=0; i<Falsepp.size(); i++) if(!Falsepp[i].empty()) cnt++;
cout<<cnt;
return 0;
}
후기
문제 링크 -> https://www.acmicpc.net/problem/1043
Union-Find 자료구조에 대해서 몰랐다면 풀기 어려웠을 것 같다.
STL에 포함되어 있지 않은 자료 구조들도 더욱 공부해야 할 것 같다.
본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.
오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!
'PS' 카테고리의 다른 글
[백준] 1918번 후위 표기식 C++ 풀이 (0) | 2024.10.10 |
---|---|
[백준] 1991번 트리 순회 C++ 풀이 (0) | 2024.10.08 |
[백준] 2206번 벽 부수고 이동하기 C++ 풀이 (0) | 2024.10.04 |
[백준] N과 M (12) C++ 풀이 (0) | 2024.09.20 |
[백준] 15663번 N과 M c++ 풀이 (0) | 2024.09.19 |