백준 1043 - 거짓말

www.acmicpc.net/problem/1043

1043번: 거짓말

 

 

지민이가 거짓말을 할 수 있는 파티 개수의 최댓값을 구하는 문제이다.

"어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다."

 

해당 문장에 각별히 유의하여 문제에 접근해보자.

파티에서 거짓말을 할 수 있는지 알 수 있는 여부는 진실을 모르는 사람이 모든 파티에 대해 진실을 아는 사람과 만나지 않아야 함을 알 수 있다.

 

이 문제를 인접행렬로 구현된 그래프로 풀어보자.

1. 우선 진실을 아는 사람들에 대해 진실을 알리는 노드 0번을 정의하여 0번 노드와 연결된 그래프를 구성한다.

2. 그 다음은 각 파티에 참여하는 사람들에 대해 연결함으로써 파티 참석자끼리 연결된 그래프를 생성한다.

3. 이제 만들어진 포레스트에 대해 서로가 연결될 수 있는지 확인하기 위해 플로이드 워셜 알고리즘을 수행한다. 각 그래프가 서로 연결되면 진실을 모르는 사람들과 진실을 알게되는 사람이 연결되는 것이므로 결국 모두가 진실을 알게 되는 것을 의미한다.

4. 각 파티에 대해 진실을 알게 된 사람이 있는지 검색한다. 진실을 알게 된 사람이 없으면 카운트에 1 더한다.

5. 총 카운트를 출력한다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int connexion[51][51];
int res = 0;

int main()
{
    int n, m, truth;
    cin >> n >> m >> truth;
    
    for (int p = 1; p <= n; ++p)
        connexion[p][p] = 1;
    
    for (int i = 0; i < truth; ++i)
    {
        int a; cin >> a;
        connexion[a][0] = connexion[0][a] = 1;
    }
    
    vector<vector<int>> parties(m);
    
    for (int j = 0; j < m; ++j)
    {
        int pts; cin >> pts;
        vector<int> room(pts);
        
        for (int k = 0; k < pts; ++k)
            cin >> room[k];
        
        for (int u = 0; u < pts; ++u)
            for (int v = 0; v < pts; ++v)
                connexion[room[u]][room[v]] = connexion[room[v]][room[u]] = 1;
        
        parties[j] = room;
    }
    
    for (int c = 0; c <= n; ++c)
        for (int i = 0; i <= n; ++i)
            for (int j = 0; j <= n; ++j)
                if (connexion[i][c] && connexion[c][j])
                    connexion[i][j] = 1;
    
    for (int q = 0; q < m; ++q)
    {
        bool pass = true;
        
        for (auto item : parties[q])
            if (connexion[item][0] == 1)
            {
                pass = false;
                break;
            }
        
        if (pass)
            ++res;
    }
    
    cout << res;
}

 

처음엔 유니온 파인드로 문제 해결을 시도했으나 많은 WA를 받았다.

해당 문제는 다양한 풀이가 존재하기 때문에 다른 솔루션도 찾아보면서 안목을 넓히는 것을 추천한다.