[알고리즘] 백준 1043 거짓말
14556 단어 알고리즘Union FindCC
상당히 고생했던 문제이다. 유니온 파인드라는 알고리즘을 알지 못해서 해결방법을 떠올리지 못했다.
개요
진실을 알고 있는 사람들과 같은 파티에 있는 사람들은 모두 진실을 알고 있는 사람들과 같게 된다.
풀이
처음에는 거짓말 할 수 있는 파티를 1, 없는 파티를 0으로 두어 모든 경우의 수를 탐색하려 했다. 그러니 시간 복잡도가 O(2^n)이 되어 버려 n<50인 이번 문제를 해결하지 못한다.
그러나 res변수를 파티수로 잡고 거짓말 하지 못하는 파티를 찾아내면 그 값을 -1하는 방식으로 해결하면 시간 복잡도가 O(n^3)이 되어 문제를 해결 할 수 있다.
소스코드
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <vector>
using namespace std;
int parent[51];
vector<int> knowing;
vector<vector<int> > party(50);
int res,n,m,val = 0;
int Find(int x) {
if (parent[x] == x)
return x;
return x = Find(parent[x]);
}
void Union(int x, int y) {
x = Find(x);
y = Find(y);
parent[x] = y;
}
int answer() {
int res = m;
for(const vector<int> &people : party) {
bool flag = false;
for(const int &person : people) {
if(flag) break;
for(const int &know : knowing) {
if(Find(person) == Find(know)) {
flag = true;
break;
}
}
}
if(flag) {
res--;
}
}
return res;
}
int main() {
scanf("%d %d",&n,&m);
int tmp;
scanf("%d",&tmp);
int a;
for(int i = 0;i<n;i++) {
parent[i] = i;
}
for(int i = 0;i<tmp;i++) {
scanf("%d",&a);
knowing.push_back(a);
}
for(int i = 0;i<m;i++) {
scanf("%d",&tmp);
int num,prev;
for(int j = 0;j<tmp;j++) {
if(j >= 1) {
prev = num;
scanf("%d",&num);
Union(prev,num);
}
else {
scanf("%d",&num);
}
party[i].push_back(num);
}
}
printf("%d",answer());
}
참고
사실상 코드를 배끼다시피 했다..😅 c++에서 foreach 문을 어떻게 쓰는지 몰랐었는데 이분 코드를 통해 알게되었다. c++11부터 지원하는 것 같다.
Author And Source
이 문제에 관하여([알고리즘] 백준 1043 거짓말), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@head022/알고리즘-백준-1043저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)