BOJ 1043번: 거짓말

문제 설명

과장된 얘기를 할 수 있는 파티 개수의 최댓값 구하기

🔗 문제 링크

핵심 아이디어

• 그래프를 사용해서 파티와 각 파티에 참석하는 사람들을 한 번에 입력 받고, 진실을 아는 사람들이 퍼지도록 함
• 모든 작업을 끝낸 후 파티별로 진실을 아는 사람이 있는지 여부 세기!

코드

#include <bits/stdc++.h>
using namespace std;
int n, m, k, a;
bool know[55];
vector<int> adj[55];
vector<vector<int>> parties;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    cin >> k;
    while(k--){
        cin >> a;
        know[a] = true;
    }
    
    int l;
    for(int i = 0; i < m; i++){
        vector<int> party;
        cin >> l;
        for(int i = 0; i < l; i++){
            cin >> a;
            party.push_back(a);
        } 
        parties.push_back(party);
        
        for(int x = 0; x < l; x++){
            for(int y = x+1; y < l; y++){
                adj[party[x]].push_back(party[y]);
                adj[party[y]].push_back(party[x]);
            }
        }
    }
    
    queue<int> q;
    for(int i = 1; i <= n; i++){
        if (know[i]) q.push(i);
    }
    
    while(!q.empty()){
        int cur = q.front(); q.pop();
        for(int nxt : adj[cur]){
            if (know[nxt]) continue;
            know[nxt] = true;
            q.push(nxt);
        }
    }
    
    int ans = 0;
    for(auto& party : parties){
        bool canLie = true;
        for(int person : party){
            if (know[person]){
                canLie = false;
                break;
            }
        }
        if (canLie) ans++;
    }
    
    cout << ans;
}

✨ 코드 개선 사항

• 나처럼 무식하게 파티에 온 사람들 전부 다 이어버리지 말고, 이런 방식으로 앞뒤 사람들만 연결시켜도 됨..

// Authored by : scsc3204
// Co-authored by : BaaaaaaaaaaarkingDog	

for(int i = 0; i < m; i++) {
    int no; cin >> no;

    int prv, nxt;
    cin >> prv;
    pt[i].push_back(prv);

    while(--no) {
      cin >> nxt;
      pt[i].push_back(nxt);
      adj[nxt].push_back(prv);
      adj[prv].push_back(nxt); // 동일한 파티에 참석한 앞뒤 사람끼리 간선이 연결되어있다고 생각
      swap(prv, nxt);
    }
  }

• vector<vector<int>> parties 대신 그래프처럼 vector<int> parties[55]로 선언해도 됨!

‼️ 헷갈렸던 부분

• 파티를 입력 받을 때마다 체크해도 된다고 생각했는데, 문제 조건을 보면 "어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 거짓말쟁이로 알려지게" 되기 때문에 한 번에 처리하기!!