[BOJ 1043] 거짓말 (C++)

거짓말 (Gold 4)

문제

전체 문제 보기

1043번: 거짓말

접근법

이 문제에서 진실을 모르는 사람들만 있는 파티의 수를 구해야 한다. 이 문제에서 진실은 같은 파티에 참석한 사람들에게 전파되는 특징이 있다. 파티의 참석자를 노드, 파티의 참석 정보를 인접 노드에 대한 정보, 진실이 전파되는 특징을 인접 노드 탐색으로 본다면 BFS로 풀 수 있는 문제이다.

자료구조 선택

BFS 알고리즘을 활용하여 문제를 풀어본다. BFS로 풀이하기 위하여 다음과 같은 노드를 정의할 수 있다.

• BFS에서는 방문 정보가 필요하지만, 이 문제에서는 진실을 알고 있다면 방문한 노드로 볼 수 있기 때문에 변수 fact로 방문 정보를 대체할 수 있다.
• 인접 노드의 정보는 해당 노드가 참석한 파티 정보와 / 해당 파티의 참석인원 정보로 통해 구할 수 있다.

struct Node {
    bool fact{};
    vector<int> partyID{};
};

사용할 컨테이너는 다음과 같다.

• person[] : 파티에 참석할 사람으로 Node 데이터를 가진다. 최대 50명이다.
• party[][] : 파티에 대한 정보로 첫 번째 인덱스에는 파티의 ID(0 ~ 49) / 두 번째 인덱스의 0번: 그 파티의 참석 인원 / 1 ~ 50번: 파티 참석자 index
• queue<int> q: BFS에서 활용할 큐

const int MAX = 51; 
array<Node, MAX> person; 
array<array<int, MAX>, MAX> party; //party[파티 ID][파티 참석자] 
queue<int> q;

구현

BFS 탐색 시작 노드는 데이터를 입력받는 과정에 진실을 알고 있는 사람을 모두 push한다. 그리고 BFS 탐색 시작 시 다음과 같이 탐색을 진행한다.

• 큐에 데이터가 남았다면 아래의 작업을 반복한다.
• 큐에 첫 번째 값을 꺼내 cur에 저장한다.
• cur노드가 참석한 모든 파티에 대해서
  • 각 파티마다 참석한 모든 사람에 대해서
    • 진실을 모른다면, 진실을 알리고, 그 사람의 인덱스를 큐에 삽입한다.

#include <iostream>
#include <array>
#include <vector>
#include <queue>
#define endl '\n'
using namespace std;

const int MAX = 51;
struct Node {
    bool fact{};
    vector<int> partyID{};
};


int main() {
    //입출력 성능향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    array<Node, MAX> person;
    array<array<int, MAX>, MAX> party; //party[파티 ID][파티 참석자]
    queue<int> q;

    int N, M; // N(사람 수), M(파티 수)은 50 이하의 자연수
    cin >> N >> M;

    int num;
    cin >> num;
    for (int i = 0; i < num; ++i)
    {
        int input;
        cin >> input;
        person[input].fact = true;
        q.push(input);
    }

    for (int i = 0; i < M; ++i)
    {
        // i 번 파티 참석자 수
        cin >> party[i][0];
        for (int j = 1; j <= party[i][0]; ++j)
        {
            // i번 파티 참석자 정보
            cin >> party[i][j];
            person[party[i][j]].partyID.push_back(i);
        }
    }

    // BFS
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        for (int ID : person[cur].partyID)
        {
            for (int i = 1; i <= party[ID][0]; ++i)
            {
                int index = party[ID][i];
                if (person[index].fact == false)
                {
                    person[index].fact = true;
                    q.push(index);
                }
            }
        }
    }

    int answer{};
    for (int i = 0; i < M; ++i)
    {
        // 파티 참석자는 최소 1명 이상
        int index = party[i][1];
        if (person[index].fact == false)
            answer++;
    }
    cout << answer;

    return 0;
}

성능 평가

시간 복잡도를 평가하기 위해서 가장 시간복잡도가 높은 BFS 반복문을 살펴보자. 첫번째 while문은 큐에 중복된 노드가 들어가지는 않기 때문에 전체 노드의 개수(\(N\)) 만큼 반복된다. 두 번째 반복문 for문은 비록 이중 반복문 형태로 들어가있지만, 전체 반복횟수는 파티 참석자의 전체 수 만큼 반복됨을 확인 할 수 있다. 여기서는 파티 참석자 수가 곧 간선의 수\(E\)와 같은 의미이다. 따라서 전체 시간 복잡도는 \(O(N + E)\)이다. 공간 복잡도는 전체 파티 정보를 저장하기 위해서 \(O(N^2)\) 크기의 배열을 사용하였다.