[백준 1043] 거짓말 (C++)PS/백준 알고리즘[BOJ]2024. 4. 8. 14:35
Table of Contents
728x90
반응형
1. 문제
https://www.acmicpc.net/problem/1043
2. 풀이
접근 방법
문제의 조건 중
"어떤 파티에서는 진실을 듣고 또다른 파티에서는 과장된 이야기를 들었을 때에도 거짓말 쟁이로 간주된다"
라는 표현이 핵심 포인트입니다. 저는 이 문제를 해결하는 과정에서 유니온 파인드를 떠올렸습니다.
처음에는 단순히 모든 파티들을 탐색하며 진실/거짓 여부를 확인하고 개수를 세어 주려고 했습니다. 하지만 테스트 케이스를 검증하다가 보니 예외가 존재합니다. 현재 사실을 아는 사람이 없어서 거짓을 말하더라도 이후에 문제가 발생합니다. 다음의 테스트 케이스를 가정해 보겠습니다.
6 4
3 1 2 3
2 1 3
1 4 6
1 5
2 4 1
위의 상황에서 진실을 아는 사람은 {1, 2, 3}이고 총 4번의 파티를 진행합니다.
- 첫 번째 파티에서는 1, 3모두 진실을 알고 있으므로 진실을 말합니다.
- 두 번째 파티에서는 거짓, 세 번째 파티에서도 거짓을 말합니다.
- 네 번째 파티에서는 진실을 아는 1이 있으므로 진실을 말해야 합니다. 여기서 문제가 생깁니다.
이미 두 번째 파티에서 4번에게 거짓을 말했는데 네 번째 파티에서 1때문에 진실을 말하면 4에 의해 거짓말쟁이가 됩니다!
이런 경우 두 번째 파티에 참여했던 4와 6모두 진실로 업데이트해야 합니다.
풀이
여기서 4와 연결되어 있는 사람들을 모두 탐색하며 업데이트시킬 수 있지만 유니온 파인드를 사용하면 O(1)로 업데이트할 수 있습니다. 따라서 집합의 개념을 이용하여 진실을 아는 집합/그 외의 집합으로 분리하고 이후에 수정이 필요한 경우 루트 노드만 업데이트하면 됩니다.
3. 구현
유니온 파인드를 이용하여 구현한 알고리즘 순서입니다.
- 진실을 아는 사람들의 집합의 루트 노드를 0, 거짓인 경우 루트노드를 자기 자신으로 정합니다.
- 각파티를 입력받으면서 파티에 참여한 사람들끼리 집합을 생성합니다.
- 이후 각 파티들을 탐색하며 한명이라도 진실을 아는 사람이 있으면 그 집합의 루트 노드를 0(진실)로 업데이트합니다.
- 마지막으로 각 파티를 탐색하며 그 파티의 집합이 거짓을 나타내는 경우를 세어 답을 출력합니다.
#include<iostream>
#include<vector>
using namespace std;
int N, M, T, ans;
//루트 노드가 0이라면 진실, 아니라면 거짓
int par[51];
vector<vector<int>> party(51);
int Find(int x) {
return x == par[x] ? x : par[x] = Find(par[x]);
}
void Union(int x, int y) {
x = Find(x);
y = Find(y);
par[y] = x;
}
int main(void) {
cin.tie(0);
ios_base::sync_with_stdio(0);
cin >> N >> M >> T;
//루트 노드 초기화
for (int i = 1; i <= N; i++) par[i] = i;
while (T--) {
int x;
cin >> x;
Union(0, x);
}
for (int i = 1; i <= M; i++) {
int n, t;//파티원 수, 파티에서 말한 진실/거짓여부
t = -1;
cin >> n;
for (int j = 1; j <= n; j++) {
int x;
cin >> x;
party[i].push_back(x);//파티원 기록 -> 이후 정답 찾기
if (!Find(x)) t = 0; //파티원중 한명이라도 진실을 아는 경우 t = 0
}
if (t != 0) t = Find(party[i][0]);
for (int j = 0; j < n; j++) Union(t, party[i][j]);
}
//정답 찾기
for (int i = 1; i <= M; i++) {
int x = party[i][0];
if (Find(x)) ans++;
}
cout << ans;
return 0;
}
4. 정리
이 문제처럼 어떤 집합들을 만들고 대표하는 정보를 저장할 때 유니온 파인드를 사용하면 O(1)로 정보를 가져올 수 있습니다.
728x90
반응형
'PS > 백준 알고리즘[BOJ]' 카테고리의 다른 글
[백준 1562] 계단수 (C++) (0) | 2024.04.19 |
---|---|
[백준 10844] 쉬운 계단 수 (C++) (0) | 2024.04.18 |
[백준 11399] ATM (C++) (0) | 2024.03.20 |
[백준 11054번] 가장 긴 바이토닉 부분 수열 (C++) (0) | 2024.01.08 |
[백준 1238번] 파티 (C++) (1) | 2024.01.04 |
@BE_개발자 :: 경이로운 개발일기
경이로운 BE 개발자가 되기 위한 프로그래밍 공부 기록장
도움이 되었다면 "❤️" 또는 "👍🏻" 해주세요! 문의는 아래 이메일로 보내주세요.