[백준/C++] 1043번 거짓말 BFS 풀이

---

문제를 읽고 testcase를 쭉 훑어보니 결국 진실을 알고 있는 사람과 연결되지 않은 사람들로만 구성된 파티를 찾아내는 것으로 인식했다.

 

먼저 진실을 알고 있는 사람을 queue에 넣고 같은 파티를 edge로 판단했다.

이후 연결된 모든 사람들을 BFS로 미리 찾는 것을 생각했다. 이후 파티 명단을 보면서 아까 BFS를 통해 찾아낸 사람이 1명이라도 있다면 거짓말을 칠 수 없다고 코드를 짜고 실행시켰는데 한번에 통과를 받았다.

 

알고보니 이 문제는 유니온파인드(분리집합)문제인데 알고나서 문제를 보니 정말 그랬다. 다음에 시간나면 유니온파인드로도 풀어서 풀이를 올려야겠다.

---

#include <bits/stdc++.h>
using namespace std;
queue<int> que ;
vector<int> party[51] ;
int graph[51][51] ;
bool check[51] ;
int N, M, cnt ;

void BFS()
{
    while(!que.empty())
    {
        int fnt = que.front() ;
        que.pop() ;

        for(int i = 1 ; i <= N ; i++)
            if(!check[i] && graph[fnt][i])
            {
                check[i] = 1 ;
                que.push(i) ;
            }
    }
}

void get_answer()
{
    BFS() ;

    int answer = 0 ;
    for(int i = 0 ; i < M ; i++)
    {
        bool flag = 1 ;
        for(int j = 0 ; j < party[i].size() ; j++)
            if(check[party[i][j]])
            {
                flag = 0 ;
                break ;
            }
         
        if(flag) answer++ ;
    }

    cout << answer << '\n' ;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0) ;
    cin >> N >> M >> cnt ;
    for(int i = 0 ; i < cnt ; i++)
    {
        int tmp ;
        cin >> tmp ;
        check[tmp] = 1 ;
        que.push(tmp) ;
    }

    for(int i = 0 ; i < M ; i++)
    {
        cin >> cnt ;
        for(int j = 0 ; j < cnt ; j++)
        {
            int tmp ;
            cin >> tmp ;
            party[i].push_back(tmp) ;
        }

        for(int j = 0 ; j < party[i].size() ; j++)
            for(int k = 0 ; k < party[i].size() ; k++)
                if(j != k) graph[party[i][j]][party[i][k]] = graph[party[i][k]][party[i][j]] = 1 ;
    }
    get_answer() ;
}

---

느낀점: 알고리즘이 익숙해졌으면 좋겠다. 좀 구현이 귀찮았는데 재밌는 문제였다.

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

1043번: 거짓말