STUDY/Algorithm

[백준] 1043 거짓말, C++

sinawi95 2022. 10. 12. 18:00
728x90
 

1043번: 거짓말

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게

www.acmicpc.net

문제 요약

진실을 모르는 파티의 최대 개수 출력

접근

1. union find

union find로 풀어야될거같았다.
입력받을 때 같은 파티에 있는 사람들끼리 union 시킨다.

for (size_t i = 1; i < M + 1; i++)
{
    int length;
    cin >> length;
    party[i][0] = length;

    for (size_t j = 1; j < length + 1; j++)
    {
        cin >> party[i][j];
        if (j == 1) continue;
        unionAB(party[i][j-1], party[i][j]);
    }
}
  • 처음엔 하나를 고정시켜놓고 union 했는데 잘 안풀렸다.
  • 이웃한 사람끼리 union을 진행했다.

입력이 끝난 이후에 모든 파티를 순회하면서 find로 진실을 모르는 파티가 있는지 확인한다.

void check()
{
    for (size_t i = 1; i < M + 1; i++)
    {
        int length = party[i][0];
        int break_chk = 0;

        for (size_t j = 1; j < length + 1; j++)
        {
            if (knowTruth[find(party[i][j])])
            {
                break_chk = 1;
                break;
            }
        }

        if (!break_chk)
        {
            answer += 1;
        }
    }
}

알고리즘

  1. find본인을 가리키고 있으면 본인의 번호를, 본인이 아닌 번호를 가리키고 있으면 최상위 노드를 반환한다.
  2. int find(int A) { if (p[A] == A) return A; p[A] = find(p[A]); return p[A]; }
  3. union두 노드가 가리키고 있는 최상위 노드로 업데이트하고, 둘중에 하나가 진실을 알고있으면 둘다 true로 갱신한다.
  4. void unionAB(int A, int B) { A = find(A); B = find(B); p[B] = A; if (knowTruth[A] || knowTruth[B]) { knowTruth[A] = 1; knowTruth[B] = 1; } }

전체 코드

#include <iostream>

using namespace std;

#define MAX 51

int N, M, numTruth, answer;
int p[MAX], knowTruth[MAX];
int party[MAX][MAX];

int find(int A)
{
    if (p[A] == A)
        return A;

    p[A] = find(p[A]);
    return p[A];
}

void unionAB(int A, int B)
{
    A = find(A);
    B = find(B);
    p[B] = A;
    if (knowTruth[A] || knowTruth[B])
    {
        knowTruth[A] = 1;
        knowTruth[B] = 1;
    }
}

void init()
{
    cin >> N >> M;
    for (size_t i = 1; i < N + 1; i++)
    {
        p[i] = i;
    }

    cin >> numTruth;    
    for (size_t i = 0; i < numTruth; i++)
    {
        int num;
        cin >> num;
        knowTruth[num] = 1;
    }

    for (size_t i = 1; i < M + 1; i++)
    {
        int length;
        cin >> length;
        party[i][0] = length;

        for (size_t j = 1; j < length + 1; j++)
        {
            cin >> party[i][j];
            if (j == 1) continue;
            unionAB(party[i][j-1], party[i][j]);
        }
    }
}

void check()
{
    for (size_t i = 1; i < M + 1; i++)
    {
        int length = party[i][0];
        int break_chk = 0;

        for (size_t j = 1; j < length + 1; j++)
        {
            if (knowTruth[find(party[i][j])])
            {
                break_chk = 1;
                break;
            }
        }

        if (!break_chk)
        {
            answer += 1;
        }
    }
}

int main()
{
    init();
    check();
    cout << answer << endl;
    return 0;
}
저작자표시