[백준] 1043번_거짓말 C++

29 Mar 2023 in Study on Coding Test

일부 과정에서 BFS나 DFS를 사용해서 푸는 문제

정답제출코드

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

using namespace std;

struct Person
{
    bool DoesKnow;
    int num;
    vector<int> PartyWith = {};

    Person(int _num, bool _Know):
    num(_num), DoesKnow(_Know){}
};

int N, M, KnowTruth;
vector<Person> People;
vector<vector<int>> PartyPeople;
bool visited[51] = {false};

bool alreadyIn(vector<int> With, int index)
{
    for (size_t i = 0; i < With.size(); ++i)
    {
        if (With[i] == index)
            return true;
    }
    return false;
}

bool CheckParty(vector<int> Party)
{
    for (size_t i = 0; i < Party.size(); ++i)
    {
        if (People[Party[i]].DoesKnow)
            return false;
    }
    return true;
}

void bfs(int start)
{
    queue<int> q;
    q.push(start);

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

        for (size_t i = 0; i < People[_index].PartyWith.size(); ++i)
        {
            int nextIndex = People[_index].PartyWith[i];
            if (!visited[nextIndex])
            {
                People[nextIndex].DoesKnow = true;
                q.push(nextIndex);
                visited[nextIndex] = true;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    
    // 사람 세팅
    Person Padding(0, false);
    People.push_back(Padding);

    for (int i = 1; i <= N; ++i)
    {
        Person P(1, false);
        People.push_back(P);
    }

    // 진실을 아는 사람 세팅
    cin >> KnowTruth;

    for (int i = 0; i < KnowTruth; ++i)
    {
        int _input;
        cin >> _input;

        People[_input].DoesKnow = true;
    }

    // 각 파티마다 누가 파티에 참가하는지 세팅
    for (int i = 0; i < M; ++i)
    {
        int Join;
        cin >> Join;
        vector<int> JoinPeople;

        for (int j = 0; j < Join; ++j)
        {
            int _input;
            cin >> _input;

            JoinPeople.push_back(_input);
        }
        PartyPeople.push_back(JoinPeople);
    }

    // 예외처리 : 진실을 아는 사람이 없으면 파티개수 그대로 출력 후 종료
    if (KnowTruth == 0)
    {
        cout << M;
        return 0;
    }

    // 각 파티마다 같이 파티에 참가하는 사람 연결
    for (size_t i = 0; i < PartyPeople.size(); ++i)
    {
        for (size_t j = 0; j < PartyPeople[i].size(); ++j)
        {
            int _index = PartyPeople[i][j];
            
            for (size_t k = 0; k < PartyPeople[i].size(); ++k)
            {
                if (_index == PartyPeople[i][k] || alreadyIn(People[_index].PartyWith, PartyPeople[i][k]))
                    continue;
                
                People[_index].PartyWith.push_back(PartyPeople[i][k]);
            }
        }
    }

    // 같이 파티에 참가하는 사람들이 진실을 아는 경우 true로 변환
    for (int i = 1; i <= N; ++i)
    {
        if (People[i].DoesKnow)
        {
            memset(visited, false, sizeof(visited));
            bfs(i);
        }
    }
    

    int ans = 0;

    // 모두 진실을 모르는 사람만 있는 파티가 몇개인지 체크
    for (size_t i = 0; i < PartyPeople.size(); ++i)
    {
        if (CheckParty(PartyPeople[i]))
            ans++; 
    }

    cout << ans;

    return 0;
}

우선, 사람을 이루는 구조체를 형성하였다. 구조체의 내용은 아래와 같다.

순번
진실을 아는가 여부
M번의 파티동안 파티에서 만나는 사람들 목록

이 문제의 핵심은 두 가지 였던 것 같다.

어떤 사람이 M번의 파티동안 누구를 만나는지를 연결하는 것.
진실을 아는사람이 있다면 그 그룹 내의 모두는 진실을 안다고 체크하는 것.

첫 번째를 이루는데에는 아래와 같은 코드를 사용하였다.

// 각 파티마다 같이 파티에 참가하는 사람 연결
for (size_t i = 0; i < PartyPeople.size(); ++i)
{
    for (size_t j = 0; j < PartyPeople[i].size(); ++j)
    {
        int _index = PartyPeople[i][j];
        
        for (size_t k = 0; k < PartyPeople[i].size(); ++k)
        {
            if (_index == PartyPeople[i][k] || alreadyIn(People[_index].PartyWith, PartyPeople[i][k]))
                continue;
            
            People[_index].PartyWith.push_back(PartyPeople[i][k]);
        }
    }
}

PartyPeople이 입력받은 각 파티마다 참가하는 사람들의 목록이다.

2중 for문을 돌리면서 어떤 사람이 총 M번의 파티동안 누구를 만나는지를 push하였다.

시간 절약을 위해 이미 있는 사람이라면 건너뛰도록 continue를 넣어주었다.

already함수는 아래와 같다.

bool alreadyIn(vector<int> With, int index)
{
    for (size_t i = 0; i < With.size(); ++i)
    {
        if (With[i] == index)
            return true;
    }
    return false;
}

그리고 대망의 두번째, 진실을 아는 사람과 같은 그룹 내에 속한 사람들은 모두 진실을 안다고 체크하는 것이다.

이 과정에서는 BFS를 사용하였다.

시작점은 진실을 아는 사람에서 시작하도록 하였고, 같은 그룹내에 있는 사람들은 모두 진실을 알도록 구현하였다.

bool visited[51] = {false};

void bfs(int start)
{
    queue<int> q;
    q.push(start);

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

        for (size_t i = 0; i < People[_index].PartyWith.size(); ++i)
        {
            int nextIndex = People[_index].PartyWith[i];
            if (!visited[nextIndex])
            {
                People[nextIndex].DoesKnow = true;
                q.push(nextIndex);
                visited[nextIndex] = true;
            }
        }
    }
}

...(중략)...


// 같이 파티에 참가하는 사람들이 진실을 아는 경우 true로 변환
for (int i = 1; i <= N; ++i)
{
    if (People[i].DoesKnow)
    {
        memset(visited, false, sizeof(visited));
        bfs(i);
    }
}

그리고 마지막에서는 모두 진실을 모르는 그룹이 몇개인지를 체크하면서 마무리를 지어주었다.

오답제출코드

#include <iostream>
#include <vector>

using namespace std;

struct Person
{
    bool DoesKnow;
    int num;
    vector<int> PartyWith = {};

    Person(int _num, bool _Know):
    num(_num), DoesKnow(_Know){}
};

int N, M, KnowTruth;
vector<Person> People;
vector<vector<int>> PartyPeople;

bool CheckParty(vector<int> Party)
{
    for (size_t i = 0; i < Party.size(); ++i)
    {
        if (People[Party[i]].DoesKnow)
            return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    
    // 사람 세팅
    Person Padding(0, false);
    People.push_back(Padding);

    for (int i = 1; i <= N; ++i)
    {
        Person P(1, false);
        People.push_back(P);
    }

    // 진실을 아는 사람 세팅
    cin >> KnowTruth;

    for (int i = 0; i < KnowTruth; ++i)
    {
        int _input;
        cin >> _input;

        People[_input].DoesKnow = true;
    }

    // 각 파티마다 누가 파티에 참가하는지 세팅
    for (int i = 0; i < M; ++i)
    {
        int Join;
        cin >> Join;
        vector<int> JoinPeople;

        for (int j = 0; j < Join; ++j)
        {
            int _input;
            cin >> _input;

            JoinPeople.push_back(_input);
        }
        PartyPeople.push_back(JoinPeople);
    }

    // 예외처리 : 진실을 아는 사람이 없으면 파티개수 그대로 출력 후 종료
    if (KnowTruth == 0)
    {
        cout << M;
        return 0;
    }

    // 각 파티마다 같이 파티에 참가하는 사람 연결
    for (size_t i = 0; i < PartyPeople.size(); ++i)
    {
        for (size_t j = 0; j < PartyPeople[i].size(); ++j)
        {
            int _index = PartyPeople[i][j];
            
            for (size_t k = 0; k < PartyPeople[i].size(); ++k)
            {
                if (_index == PartyPeople[i][k])
                    continue;
                
                People[_index].PartyWith.push_back(PartyPeople[i][k]);
            }
        }
    }

    // 같이 파티에 참가하는 사람들이 진실을 아는 경우 true로 변환
    for (int l = 0; l < 2; ++l)
    {
        for (int i = 1; i <= N; ++i)
        {
            for (size_t j = 0; j < People[i].PartyWith.size(); ++j)
            {
                int _index = People[i].PartyWith[j];
                if (People[_index].DoesKnow)
                {
                    People[i].DoesKnow = true;
                }
            }
        }

        for (int i = N; i >= 1; --i)
        {
            for (size_t j = 0; j < People[i].PartyWith.size(); ++j)
            {
                int _index = People[i].PartyWith[j];
                if (People[_index].DoesKnow)
                {
                    People[i].DoesKnow = true;
                }
            }
        }
    }
    

    int ans = 0;

    // 모두 진실을 모르는 사람만 있는 파티가 몇개인지 체크
    for (size_t i = 0; i < PartyPeople.size(); ++i)
    {
        if (CheckParty(PartyPeople[i]))
            ans++; 
    }

    cout << ans;

    return 0;
}

정답코드와 비교하면 진실을 아는 사람과 연결된 사람들에게 DoesKnow을 true로 바꿔주는 과정이 잘못되었다.

나는 처음엔 양방향으로 2회 순회를 하면서 어떤 사람의 같이 파티에 참가하는 사람 중에 진실을 아는 사람이 있으면 그 어떤 사람도 진실을 아는 것으로 바꿔주었다.

즉, BFS를 사용하지 않았다. 이것도 확실한 방법이라고 생각을 했는데 그렇지는 않았나보다.

반례는 모르겠지만 BFS에 비해서는 확실하지 않은 방법이긴하지.

// 같이 파티에 참가하는 사람들이 진실을 아는 경우 true로 변환
    for (int l = 0; l < 2; ++l)
    {
        for (int i = 1; i <= N; ++i)
        {
            for (size_t j = 0; j < People[i].PartyWith.size(); ++j)
            {
                int _index = People[i].PartyWith[j];
                if (People[_index].DoesKnow)
                {
                    People[i].DoesKnow = true;
                }
            }
        }

        for (int i = N; i >= 1; --i)
        {
            for (size_t j = 0; j < People[i].PartyWith.size(); ++j)
            {
                int _index = People[i].PartyWith[j];
                if (People[_index].DoesKnow)
                {
                    People[i].DoesKnow = true;
                }
            }
        }
    }

[백준] 1043번_거짓말 C++

정답제출코드

오답제출코드

우키의 일지

Error

정답제출코드

오답제출코드

Templates (for web app):

Error