진짜 사람 찾기

몇 번 사람이 몇 명을 알고 그 번호의 사람을 메모장에 표시하는 과제였습니다.

#include <iostream>
#include <fstream>
#include <chrono>
#include <vector>
#include <list>

using namespace std;

struct Human
{
    int id;
    int knowNum;
    int* realHuman;
    bool check = false;
    void Print()
    {
        cout << "id :" << id << "\t";
        cout << "knowNum :" << knowNum << "\t";
        for (int i = 0; i < knowNum; i++)
            cout << "realHuman :" << realHuman[i] << "\t";

        cout << endl;
    }
};

int main()
{
    std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
    ifstream fin;
    fin.open("마을2.txt", ios::in);
    int villageSize;
    fin >> villageSize;
    Human* village = new Human[villageSize + 1];

    for (int i = 1; i < villageSize + 1; i++)
    {
        fin >> village[i].id;
        fin >> village[i].knowNum;
        village[i].realHuman = new int[village[i].knowNum];
        for (int j = 0; j < village[i].knowNum; j++)
        {
            fin >> village[i].realHuman[j];
        }
    }
    
    list<int> findlist;
    village[1].check = true;
    findlist.push_back(1);

    while (not findlist.empty())
    {
        int id = findlist.front();
        for (int i = 0; i < village[id].knowNum; i++)
        {
            int idx = village[id].realHuman[i];
            if (not village[idx].check)
            {
                findlist.push_back(idx);
                village[idx].check = true;
            }
        }
        findlist.pop_front();
    }

    int count = 0;
    for (int i = 1; i < villageSize + 1; i++)
    {
        if (village[i].check)count++;
    }
    std::chrono::duration<double>sec = std::chrono::system_clock::now() - start;
    cout << "마을1:" << count << "명 실행시간:" << sec.count() << "초" << endl;
}

코드입니다.

마을1.txt

0.00MB

마을2.txt

2.40MB

그럼 메모장에 이런 형식으로 나오게 됩니다.

 

읽어주셔서 감사합니다.