백준 - 1043

문제

https://www.acmicpc.net/problem/1043

1043번: 거짓말

구라쟁이 지민이를 위해 그룹을 만들어 해결하는 문제였다.

 

문제 풀이

처음 문제를 봤을 때는 진실을 아는 사람들을 vector에 집어넣고 while로 더 이상 들어가지 않을 때까지 돌린 후,  마지막에 각 파티마다 확인하는 방법을 생각했다. 코드로 옮기기 전부터 너무 비효율적인 것 같아 고민하던 찰나에 유니온 파인드가 생각났고, parent를 만들어서 푸는 방법을 떠올렸다.

 

1. 진실을 아는 사람들의 parent를 0으로 만들기
2. parent가 0이 아닐 경우 각 파티의 맨 앞을 parent로 만들기
3. 각 파티마다 parent check를 하기 (값이 더이상 변경되지 않을 때까지 반복)

 

이렇게 순서를 생각하고 문제를 풀었는데, 자동으로 0으로 채워져서 2번이 실행되지 않아 진실 사람들의 vector를 만들고 party vector를 입력받은 후에 parent를 바꿔줬다. fill을 사용하면 됐을텐데 그냥 빨리 해결하고 싶었나~

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <queue>

using namespace std;

int N, M;
vector<int> partyPeople[50];
vector<int> truthPeople;
int parent[51]; //N들의 parent, 0이면 진실

int changeParent(int index) { //party에 참여한 사람들의 parent 0으로 변경
    int i;
    int flag = 0;
    for (i = 0; i < partyPeople[index].size(); i++) {
        if (parent[partyPeople[index][i]] != 0) {
            parent[partyPeople[index][i]] = 0;
            flag = 1;
        }
    }
    return flag;
}

int renewParent() {
    int flag = 0;
    int i, j;
    for (i = 0; i < M; i++) {
        for (j = 0; j < partyPeople[i].size(); j++) {
            if (parent[partyPeople[i][j]] == 0) { //party에 참여한 사람들 중 parent가 0인 사람이 있다면 changeParent 해주기
                if(changeParent(i) == 1)
                    flag = 1;
                break;
            }
        }
    }

    return flag; //flag 1이면 갱신된 것
}

int checkParty() {
    int i;
    int count = 0;

    for (i = 0; i < M; i++) {
        if (parent[partyPeople[i].front()] != 0) {
            count++;
        }
    }

    return count;
}

int main() {  
    int tNum;
    int i, j, t, num;
    int pa;

    scanf("%d %d", &N, &M);

    scanf("%d", &tNum);
    for (i = 0; i < tNum; i++) {
        scanf("%d", &t);
        truthPeople.push_back(t);
    }

    //party
    for (i = 0; i < M; i++) {
        scanf("%d", &num);
        for (j = 0; j < num; j++) {
            scanf("%d", &t);         
            if (j == 0) { //맨 앞일 경우
                pa = t;
            }
            parent[t] = pa;
            partyPeople[i].push_back(t);
        }
    }
    for (i = 0; i < truthPeople.size(); i++) {
        parent[truthPeople[i]] = 0;
    }

    //truth people 갱신
    while (1) {
        if (renewParent() == 0) {
            break;
        }
    }

    printf("%d", checkParty());

    return 0;
}