[C++] 백준/BOJ - 1043 : 거짓말

문제 이해 단계

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

사람 수 N과 파티의 수 M이 주어진다.
그다음줄에는 진실을 아는 사람의 번호가 주어지는데,

지민이는 모든 파티를 참석하면서 거짓말을 쳐야 한다.
하지만 진실을 아는 사람이 있는 파티에서는 무조건 진실을 말해야 한다.

진실을 들은 사람이 거짓말을 듣거나,
거짓말을 들은 사람이 진실을 들으면 이는 실패한 것이다.

해당 조건에서 지민이가 거짓말을 칠 수 있는 파티의 최대 수를 구하는 문제

 

---

문제 접근 단계

문제의 제한조건부터 살펴보자.

사람의 수 N과 파티의 수 M이 모두 50까지 가능하다.
상당히 작은 숫자라서, 완전 탐색이나 원하는 대로 풀이가 가능할 것 같다.

---

문제의 특징

이 문제의 특징적인 점은, 옳고 그름을 판단하기 위해서는
결국 마지막까지 전부 계산해야 한다는 것이다.

예제 입력 7을 보자.

3 4
1 3
1 1
1 2
2 1 2
3 1 2 3

마지막 파티에서 1번 2번 3번이
모두 한 곳에 모이게 돼서 답이 0이 되어버린다.

그렇기 때문에 한 파티 씩 판단하는 그리디 방식은 사용할 수 없을 것 같다.

---

문제 풀이 방식

그래서 나는 파티의 관점이 아닌, 진실을 아는 사람의 관점에서 봤다.

진실을 아는 사람과 같은 파티에 속한 사람들은 진실을 아는 사람이 된다.

즉, 진실된 사람들을 계속해서 추적하면 연쇄적으로
더 이상 진실된 사람이 늘어나지 않을 때까지 간다는 것이다.

그래서 아래와 같은 순서로 알고리즘을 짰다.

1. 진실을 아는 사람들을 큐에 넣는다.
2. 큐에서 한 명을 뺀다.
3. 전체 파티를 훑으면서 진실을 아는 사람이 속한 파티가 있는지 찾는다.
4. 파티가 있다면 그 파티에 속한 모든 사람을 큐에 넣고, 그 파티를 제거한다.
5. 2~4번 과정을 큐가 빌 때까지 반복한다.

즉 약간의 BFS 같은 것을 반복한다는 것이다.
자세한 로직은 문제 구현단계에서 보자.

 

---

문제 구현 단계

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N,M;
vector<vector<int>> party; // 파티의 정보

// 파티 안에 진실을 아는 사람이 포함되어있는지 판단
bool isMatch(vector<int> v,int t){
    auto it = find(v.begin(),v.end(),t);
    if(it != v.end()) return true;
    else return false;
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    cin >> N >> M;
    int num;
    cin >> num;
    queue<int> truth;
    // 진실을 아는 사람을 큐에 넣는다.
    while(num--){
        int val;
        cin >> val;
        truth.push(val);
    }
    for(int i = 0; i < M; i++){
        int n;
        cin >> n;
        vector<int> tmp;
        while(n--){
            int p;
            cin >> p;
            tmp.push_back(p);
        }
        party.push_back(tmp);
    }

    // 진실을 아는 사람이 큐에 없을때까지 반복
    while(!truth.empty()){
        // 한명씩 뺀다.
        int t = truth.front();
        truth.pop();
        // 모든 파티를 순회
        for(int i = 0; i < party.size(); i++){
            if(isMatch(party[i],t)){
                // 진실된 사람이 속한 파티
                for(auto it : party[i]) truth.push(it); // 모든 사람을 큐에 넣음
                party.erase(party.begin()+i); // 그 파티를 삭제
                i--;
            }
        }
    }
    cout << party.size();

}

전체적인 로직을 위에서 설명한 것과 같다.

먼저 입력으로 주어진 진실을 아는 사람을 큐에 넣은 채로 시작한다.

그다음 큐에서 한 명씩 빼면서
모든 파티를 순회하는 것을 반복한다.

진실된 사람이 속한 파티를 찾는 것은
isMatch라는 함수라는 이름으로 따로 빼놨다.

큐를 끝내기 위해, 매칭된 파티를 삭제하는 것을 잊지 말아야 한다.

풀이는 여기까지이다.

 

---

시행착오

푸는데 30분 정도 걸린 문제이다.
그렇게 어렵지 않게 풀었던 것 같다.

처음에는 큐를 사용해서 풀 생각은 아니었는데,
풀다 보니 큐를 쓸 생각이 들었다.

오랜만에 빠르게 푼 문제라 좋다.

https://toss.me/howudong

howudong님에게 보내주세요