Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- Unreal
- 언리얼 플러그인
- 1759번
- 트랜잭션 관리
- FBX
- oracle
- 실습
- 오손데이터읽기
- Security
- 5639
- 셰그먼트트리
- OS
- 백준
- 언리얼 커스텀 플러그인
- C++
- hackerank
- 1967번
- UnrealMP
- UActor
- Linux
- command not found
- 데이터베이스 배움터
- objtofbx
- 1253번
- 백준 1253번
- 2단계로킹
- 민겸수
- 의미와 무의미의 경계에서
- 비재귀셰그먼트
- SQL
Archives
- Today
- Total
fatalite
거짓말 - 백준 1043 본문
골드4
유니온 파인드 문제라는 것 같은데
나는 그래프 탐색처럼 풀었다.
나중에 유니온 파인드 복습해야겠다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
// n,m
int n, m;
cin >> n >> m;
int q;
cin >> q;
vector<int> known;
vector<bool> bKnown(n,false);
vector<bool> bDay(m, false);
for (int i = 0; i < q; i++) {
int c;
cin >> c;
known.push_back(c-1);
}
vector<vector<bool>> bPartys = vector<vector<bool>>(m, vector<bool>(n, false));
for (int i = 0; i < m; i++) {
int k = 0;
cin >> k;
for (int u = 0; u < k; u++) {
int p;
cin >> p;
bPartys[i][p-1] = true;
}
}
while (!known.empty()) {
int w = known.back();
bKnown[w] = true;
known.pop_back();
vector<int> days;
for (int i = 0; i < m; i++) {
if (bPartys[i][w] == true) {
if (bDay[i] == false) {
days.push_back(i);
bDay[i] = true;
}
}
}
for (int a : days) {
for (int i = 0; i < n; i++) {
if (bPartys[a][i] == true) {
if (bKnown[i] == false) {
known.push_back(i);
}
}
bPartys[a][i] = true;
}
}
}
int cnt = 0;
for (int i = 0; i < m; i++) {
for (int k = 0; k < n; k++) {
if (bPartys[i][k] == false) {
cnt++;
break;
}
}
}
int cntd = 0;
for (int i = 0; i < m; i++) {
if (bDay[i] == false) {
cntd++;
}
}
cout << cntd;
//cout << endl;
//cout << cnt;
}
'코딩 인터뷰 > C++' 카테고리의 다른 글
N과 M(4) - 백준 15652 (0) | 2023.02.26 |
---|---|
최소비용 구하기 - 1916 백준 (0) | 2023.02.13 |
RGB 거리 - 백준 1149 (0) | 2023.02.05 |
Sales by Match (0) | 2023.02.04 |
(파이썬 풀이) XOR String 3 (0) | 2023.02.03 |