[ 백준 ] 1043 / 거짓말

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
223/228
post-thumbnail

# Appreciation

/*
 * Problem :: 1043 / 거짓말
 *
 * Kind :: Union Find
 *
 * Insight
 * - 그러니까...
 *   진실은 아는 사람들이 있고
 *   이 사람들이 속한 파티에 있는 다른 사람들도 진실을 아는 사람들이 되며
 *   진실을 모르는 사람들끼리 이루어진 파티가 몇 개인지를 찾아야 한다
 *   + 파티에 오는 사람들끼리 같은 집합에 속하게 하고
 *     진실을 아는 사람들의 루트 노드(대표값)들을 확인한 후
 *     각 파티 사람들의 루트 노드가 위의 노드인지 아닌지를 확인해주자
 *     # Disjoint Set(서로소 집합)으로 풀어야 겠다
 *       Union Find 알고리즘을 활용하자
 *
 * Point
 * - 짧고 의미집약적인 좋은 변수명을 찾는게 너무 어렵다...
 *   + 변수명 잘 짓는 법좀 공부해야 겠다
 *     # 클린 코드(Clean Code)라는 좋은 책도 있던데 읽어봐야겠다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int P[50+1], R[50+1];

// Set up : Functions Declaration
int find(int x);
void merge(int x, int y);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N, M;
    cin >> N >> M;
    int K; cin >> K;
    int T[K]; /* 진실을 아는 사람의 번호가 저장된 배열 */
    for (int i=0; i<K; i++)
        cin >> T[i];
    vector<int> PTY[M]; /* PTY[i] = i 번째 파티에 오는 사람들이 저장된 Vector */
    for (int i=0; i<M; i++) {
        int num; cin >> num;
        for (int j=0; j<num; j++) {
            int no; cin >> no;
            PTY[i].push_back(no);
        }
    }

    // Control : Output
    if (K == 0) { /* 만약 진실을 아는 사람들이 아무도 없다면 */
        cout << M << endl; /* 모든 파티에 참석 가능 */
        exit(0);
    }

    // Process
    for (int i=1; i<=N; i++) { /* Union Find 관련 배열 초기화 */
        P[i] = i;
        R[i] = 1;
    }

    for (int i=0; i<M; i++) {
        vector<int> pty = PTY[i]; /* i 번째 파티 참석자들 */
        int size = pty.size(); /* 파티 참가자수 */
        if (size > 1) { /* 파티 참가자수가 1명 초과일 때 */
            for (int j=1; j<size; j++) { /* 파티에 오는 사람들이
                                          * 모두 같은 집합에 속하도록 만듦 */
                if (find(pty[0]) != find(pty[j])) {
                    merge(pty[0], pty[j]);
                }
            }
        }
    }

    set<int> S; /* 진실을 아는 사람들이 속한 집합의 루트 노드가 저장된 Set */
    for (int t : T) {
        S.insert(find(t));
    }

    int ans = 0; /* 참석할 수 있는 파티의 수 */
    for (int i=0; i<M; i++) {
        vector<int> pty = PTY[i]; /* i 번째 파티 참석자들 */
        /* 파티에 오는 사람들이 아무도 없으면 참석 가능 */
        if (pty.empty()) { ans++; continue; }
        /* 파티에 오는 사람들 중 임의로 한 사람을 뽑음
         * 파티에 오는 사람들 모두 같은 집합에 속한 상태 */
        int p = find(pty.front()); /* 편의상 파티에 오는 사람들 중
                                    * 첫번째 참가자를 선택 */
        /* 그 사람의 루트 노드가 진실을 아는 사람들이 속한 집합의 루트 노드가 아니라면 */
        if (S.find(p) == S.end()) {
            ans++; /* 참석할 수 있는 파티의 수 증가 */
        }
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
int find(int x)
/* Union Find 알고리즘의 Find 를 구현한 함수 */
{
    if (P[x] == x) return x;
    return P[x] = find(P[x]);
}

void merge(int x, int y)
/* Union Find 알고리즘의 Union 를 구현한 함수 */
{
    x = find(x);
    y = find(y);

    if (R[x] < R[y])
        swap(x, y);

    P[y] = x;
    if (R[x] == R[y])
        R[x]++;
}
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글