[baekjoon/C++] 백준 1043_거짓말

 

 

백준 1043

난이도 ; Gold 4

문제 링크 ; https://www.acmicpc.net/problem/1043

 

1043번: 거짓말

 

 

풀이/사고 과정

 

지민이가 진실을 아는 사람들을 피해 파티 사람들에게 거짓말을 할 수 있도록 도와주는 문제.

문제 해결에 중요한 부분은 "어떤 사람이 어떤 파티에서는 진실을 듣고,

또 다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다."였다.

파티에 진실을 아는 사람이 있다면, 그 파티에 있는 모든 사람이 참석하는 다른 파티에서도 지민이는 진실만 말해야 한다.

따라서 각 파티에 참석한 사람들을 같은 그룹으로 묶고, 진실을 아는 사람과 같은 그룹이라면

지민이가 거짓말을 할 수 없다는 점을 통해 결과를 출력하면 된다.

 

처음에 그래프가 떠오르긴 했지만, 알고 있는 알고리즘들 중에서는 마땅히 이거 써야겠다 하는 게 없어서 구글링을 해봤다.

트리&그래프 부분 진도 나가던 중일 때 자료구조 재수강하려고 마음먹고 공부 안 했더니 백준 문제 풀 때 걸리는 부분이 많아서 얼른 혼자서라도 다시 공부해야 할 것 같다.ㅎ

 

이 문제에서는 Union-Find 알고리즘이 사용됐다.

우선, 진실을 아는 사람들을 입력받아 벡터에 저장한다.

그다음에는 각 파티에 참석하는 사람들을 같은 그래프로 묶는다.

그리고 파티에 온 사람들과 진실을 아는 사람이 같은 그래프에 속해있다면(같은 root 노드라면),

거짓말을 할 수 있는 파티의 수(M)를 줄인다.

 

 

코드

 

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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

#include <iostream> #include <vector>   using namespace std;   int parents[51]; vector <int> know; vector <vector<int>> party(50);   int Find(int x) {     if (parents[x] == x) return x; //x의 부모가 x와 같은 경우, 자기 자신 return     return x = Find(parents[x]); //그렇지 않다면 루트 노드를 찾을 때까지 재귀적으로 탐색 }   void Union(int a, int b) {     a = Find(a);     b = Find(b);     parents[a] = b; }   int main() {     ios_base::sync_with_stdio(false);     cin.tie(0); cout.tie(0);       int N, M, K;       cin >> N >> M >> K; //K = 진실을 아는 사람의 수       while (K--) {         int truth; //진실을 아는 사람의 번호         cin >> truth;         know.push_back(truth); //진실을 아는 사람의 번호를 know 벡터에 push     }       for (int i = 1; i <= N; i++) { //모든 노드가 자기 자신을 가리키도록 초기화         parents[i] = i;     }       for (int i = 0; i < M; i++) {         int num, prev, member;         cin >> num; //파티에 오는 사람 수             for (int j = 0; j < num; j++) {             if (j < 1) {                 cin >> member;             }             else {                 prev = member;                 cin >> member;                 Union(prev, member); //파티에 온 사람 그룹화하기             }             party[i].push_back(member); //i번째 파티에 온 사람들을 그룹으로 저장         }     }       for (auto& list : party) {         bool flag = false;         for (auto& person : list) { //파티에 간 사람들             if (flag) break;             for (auto& truth : know) { //진실을 아는 사람들                 if (Find(person) == Find(truth)) { //파티에 간 사람이 진실을 아는 사람과 같은 루트 노드를 가지고 있다면                     flag = true; //flag는 truth                     break;                 }             }         }         if (flag) M--; //flag가 truth인 경우 거짓말을 할 수 있는 파티 수 하나 감소     }     cout << M;       return 0; } Colored by Color Scripter

cs

 

지적/댓글 언제나 환영