백준 1043번 [거짓말](C++) -yes6686- 티스토리

백준 문제 풀이: 1043 [거짓말]

---

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

문제 설명:

사람들이 파티에서 진실을 아는 사람들과 거짓말을 할 수 있는 사람들 간의 연결성을 기반으로, 진실을 아는 사람이 없는 파티의 수를 최대화하는 문제입니다.

입력:

• 첫째 줄에 사람의 수 n과 파티의 수 m이 주어집니다. (1 ≤ n, m ≤ 50)
• 둘째 줄에는 진실을 아는 사람의 수와 해당 사람들의 번호가 주어집니다.
• 셋째 줄부터 m개의 줄에는 각 파티에 참석한 사람의 수와 사람들의 번호가 주어집니다.

출력:

• 진실을 말할 필요가 없는 파티의 최대 수를 출력합니다.

예시:

입력:
4 3
1 1
2 1 2
1 3
3 2 3 4

출력:
1

---

문제 해결 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> parties[51]; // 각 파티에 참석한 사람들
vector<int> knowTruth;  // 진실을 아는 사람들
bool visitedParty[51];      // 방문한 파티
bool knowsTruth[51];        // 진실을 아는 사람

void spreadTruth(int n) {
    queue<int> q;
    for (int person : knowTruth) {
        q.push(person);
    }

    while (!q.empty()) {
        int current = q.front();
        q.pop();

        for (int i = 0; i < n; i++) {
            if (visitedParty[i]) continue;

            bool attended = false;
            for (int person : parties[i]) {
                if (knowsTruth[person]) {
                    attended = true;
                    break;
                }
            }

            if (attended) {
                visitedParty[i] = true;
                for (int person : parties[i]) {
                    if (!knowsTruth[person]) {
                        knowsTruth[person] = true;
                        q.push(person);
                    }
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    int truthCount;
    cin >> truthCount;

    for (int i = 0; i < truthCount; i++) {
        int person;
        cin >> person;
        knowTruth.push_back(person);
        knowsTruth[person] = true;
    }

    for (int i = 0; i < m; i++) {
        int attendees;
        cin >> attendees;
        for (int j = 0; j < attendees; j++) {
            int person;
            cin >> person;
            parties[i].push_back(person);
        }
    }

    spreadTruth(m);

    int result = 0;
    for (int i = 0; i < m; i++) {
        bool safeParty = true;
        for (int person : parties[i]) {
            if (knowsTruth[person]) {
                safeParty = false;
                break;
            }
        }
        if (safeParty) result++;
    }

    cout << result << '\n';
    return 0;
}

---

코드 설명

이 코드는 BFS(너비 우선 탐색)를 사용하여 진실을 아는 사람들과 연결된 모든 파티를 탐색하고, 거짓말을 말할 수 있는 파티의 수를 계산합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘:
  • 진실을 아는 사람을 시작점으로, 진실이 퍼질 수 있는 모든 파티를 BFS로 탐색합니다.
• 구현 세부사항:
  • knowsTruth: 진실을 아는 사람인지 여부를 저장하는 배열입니다.
  • visitedParty: 이미 탐색한 파티인지 여부를 저장합니다.
  • spreadTruth: BFS를 통해 진실을 퍼뜨립니다.
• 시간 복잡도 분석:
  • BFS 탐색: O(m × n) (파티와 사람 간의 연결을 모두 탐색)
  • 전체 시간 복잡도: O(m × n)

---

결과

코드는 진실을 아는 사람과 연결되지 않은 파티의 수를 정확히 계산합니다. 입력 크기가 작으므로 O(m × n) 시간 복잡도 내에서 효율적으로 작동합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!