BOJ 1043 : 거짓말 [C++]

문제

 

문제를 제대로 이해 못 해서 헤매고, 접근 방법 못 찾아서 헤매면서 50분 날렸다.

저녁 먹으면서 생각하다가 접근 방법 찾고 해결했다.

접근 방법 알고 나니 5분 만에 해결 완료.

 

// 진실을 아는 사람인지 체크
// true이면 진실을 아는 사람
bool know_truth[51] = {false, };

// 파티 번호 i에 참가하는 인원들의 번호를 vector에 보관
std::vector<int> participants[51];  

// 번호 i인 사람이 참여하는 파티의 번호를 vector에 보관
std::vector<int> party_list[51];

// bfs에 사용하기 위한 queue
std::queue<int> trace;

 

진실을 아는 사람과 같은 파티에 참석하는 사람은 진실을 알게 된다.

단순히 순회하여 이를 갱신해나간다면 순회를 꽤나 반복해야 한다.

 

1. 처음 입력으로 들어온 진실을 아는 사람부터 시작.
2. 이 사람이 참석하는 파티들의 참석인원들을 검사한다.
3. 진실을 알지 못하는 사람들은 진실을 알게 될 것이니 know_truth를 true로 바꾸어 주고 queue에 push.

위 과정을 queue가 빌 때까지 반복.

 

코드

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

bool know_truth[51] = {false, };
std::vector<int> participants[51];  // entry of participants
std::vector<int> party_list[51];    // number i's participate party
std::queue<int> trace;

void bfs() {
    while (!trace.empty()) {
        int cur_num = trace.front();
        trace.pop();

        for (int i : party_list[cur_num]) {
            for (int j : participants[i]) {
                if (!know_truth[j]) {
                    know_truth[j] = true;
                    trace.push(j);
                }
            }
        }
    }
}

int main() {
    int num_of_people = 0, num_of_party = 0;
    std::cin >> num_of_people >> num_of_party;

    int who_knows = 0;
    std::cin >> who_knows;
    if (who_knows > 0) {
        for (int i = 0; i < who_knows; i++) {
            int num = 0;
            std::cin >> num;
            know_truth[num] = true;
            trace.push(num);
        }
    }

    for (int i = 0 ; i < num_of_party; i++) {
        int people = 0;
        std::cin >> people;
        for (int j = 0; j < people; j++) {
            int num = 0;
            std::cin >> num;
            party_list[num].push_back(i);
            participants[i].push_back(num);
        }
    }

    bfs();

    int ans = 0;

    for (int i = 0; i < num_of_party; i++) {
        bool possible = true;
        for (int j : participants[i]) {
            if (know_truth[j]) {
                possible = false;
                break;
            }
        }
        if (possible) {
            ans++;
        }
    }

    std::cout << ans << "\n";

    return 0;
}

 

 

 

---

 

 

해결하고 나서 문제 분류를 보니 그래프였는데,

내가 작성한 코드도 그래프 활용으로 볼 수 있나?

 

이 글을 쓰면서 다른 사람들은 어떻게 풀었는지 검색해보는데,

유니온 파인드를 써서 푼 글이 가장 먼저 나왔다.

유니온 파인드는 들어보기만 했지 개념도 잘 모르고 한 문제도 안 풀어봤는데,

이 문제 풀이 보면서 대충 어떤 건지 감을 잡아보면 될 것 같다.

 

그리고 처음 이 문제를 봤을 때 뭔가 확실한 이유도 없었던 거 같은데 계속 map을 쓰려고 했다.

아마 우테코 프리코스 1주 차를 자바로 진행하면서 map을 많이 써서 신경이 그쪽으로 쏠렸나 보다.

가끔 이렇게 자주 쓰는 거에 꽂혀서 그거만 생각하는 경향이 짙은데, 매우 안 좋은 현상 같다.

어캐 고치노