문제 출처

1. 문제설명

  • 요약하자면 다음과 같다.
    • 지민이의 과장된 이야기의 진실을 아는 사람이 있다.
    • 어떤 파티에 진실을 아는 사람이 있다면, 거기 있는 모든 사람이 진실을 알게 된다.
    • 지민이와 다른 사람들이 M개의 파티에 참석한다.
    • 과장된 이야기의 진실을 모르는 파티의 수를 구하라


2. 알고리즘 설계

  • 값 저장
    • 진실을 아는 사람
    • M번째 파티에 참석한 사람들
    • adjacency matrix(adj) : 각 파티에 참석한 사람들은 이어져 있다고 가정
  • BFS
    • 진실을 아는 사람의 번호를 하나씩 꺼낸다.
    • adj를 통해 연결된 모든 사람이 진실을 알게 된다.
  • M번째 파티에 참석한 사람들을 모두 체크하면서, 전부 진실을 모른다면 정답값++


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ = 55;
int n, m, t, tmp, prv, nxt, ans;
bool tr[SZ];
vector<int> pt[SZ];
vector<int> adj[SZ];

void bfs() {
    queue<int> q;
    for(int i = 1; i <= n; i++)
        if(tr[i]) q.push(i);
  
    while(!q.empty()) {
        int cur = q.front(); 
        q.pop();

        for(int nxt : adj[cur]) {
            if(tr[nxt]) continue;
            tr[nxt] = 1;
            q.push(nxt);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> t;
    while(t--) {
        cin >> tmp;
        tr[tmp] = true;
    }

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

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

        while(--tmp) {
            cin >> nxt;
            pt[i].push_back(nxt);
            adj[prv].push_back(nxt);
            adj[nxt].push_back(prv);
            prv = nxt;
        }
    }

    bfs();

    for(int i=0; i<m; i++) {
        bool chk = false;
        for(int p : pt[i]) if(tr[p]) chk = true;
        if(!chk) ans++;
    }

    cout << ans;

    return 0;
}


4. 소감

  • 문제 로직 자체는 생각하는 데 얼마 안 걸렸다.
  • 문제의 입력 때문에 문제 이해하는 데 시간을 많이 투자했다.
  • 문제 이해 능력 또한 키울 필요가 있다고 느꼈다.