알고스팟 - PICNIC

algospot.com :: PICNIC

소풍 문제 답안 제출 통계 문제 정보 문제 ID 시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) PICNIC 1000 ms 65536 kb 13124 5592 ( 42 %) 출제자 출처 분류 JongMan 알고리즘 문제 해결 전략 보기 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 ...

www.algospot.com

이거 종만 아재가 완전탐색으로 풀라고 던진 문제임.

어차피 선택 문제이므로 노드를 탐색하는 순서가 하나면 됨.

예를들어서 연결된 노드의 숫자가 적은 노드부터, 혹은 많은 노드부터 순서대로 조사하는 거임.

​

​

상식적으로 적은 노드부터 하는게 더 빠를거라고 생각될 거임.

실제로 알고스팟 결과는 2배 정도 차이남.

#include <iostream>
#include <vector>
#include <algorithm>
//#include "Random.h"
class Class
{
public:
    Class() = default;
    ~Class() = default;
    friend std::istream& operator>>(std::istream& in, Class& rhs)
    {
        in >> rhs.nStudent >> rhs.nFriend;
        for (int i = 0; i < rhs.nFriend; i++)
        {
            std::pair<int, int> tmp;
            in >> tmp.first >> tmp.second;
            rhs.m_friends.emplace_back(tmp);
        }
        return in;
    }
    std::vector<int> Init_Code_Count(std::vector<std::pair<int, int>> friend_relations)
    {
        std::vector<int> code_count(nStudent);
        for (const auto& f : friend_relations)
        {
            code_count[f.first]++;
            code_count[f.second]++;
        }
        for (auto& c : code_count)
            if (c <= 0)
                c = 99999;
        return code_count;
    }
    void Do()
    {
        std::cout << Delete_Til(std::make_pair(-1, -1), Init_Code_Count(m_friends), m_friends) << std::endl;;
    }
    int Delete_Til(std::pair<int, int> choosen, std::vector<int> code_count, std::vector<std::pair<int, int>> friend_relations)
    {
        int result = 0;
        if (choosen.first != -1)
        {
            code_count[choosen.first] = 999999;
            code_count[choosen.second] = 999999;
            for (auto iter = friend_relations.begin(); iter != friend_relations.end();)
            {
                if (iter->first == choosen.first || iter->second == choosen.first ||
                    iter->first == choosen.second || iter->second == choosen.second)
                    iter = friend_relations.erase(iter);
                else
                    iter++;
            }
        }
        if (friend_relations.size() <= 0)
        {
            for (const auto& c : code_count)
            {
                if (c != 999999)
                    return 0;
            }
            return 1;
        }
        auto _min = *std::min_element(code_count.begin(), code_count.end());
        std::vector<int> _student_with_min_friends;
        for (int i = 0; i < nStudent; i++)
            if (code_count[i] == _min)
            {
                _student_with_min_friends.push_back(i);
                break;
            }
        auto a = Find(_student_with_min_friends, friend_relations);
        for (auto s : Find(_student_with_min_friends, friend_relations))
        {
            result += Delete_Til(s, code_count, friend_relations);
        }
        return result;
    }
    std::vector<std::pair<int, int>> Find(std::vector<int>& student_with_min_friends, std::vector<std::pair<int, int>>& friend_relations)
    {
        std::vector<std::pair<int, int>> results;
        for (auto f : friend_relations)
        {
            bool isChoosen = false;
            for (auto s : student_with_min_friends)
            {
                if ((f.first == s || f.second == s) && !isChoosen)
                {
                    results.emplace_back(f);
                    isChoosen = true;
                }
            }
        }
        return results;
    }
private:
    int nStudent;
    int nFriend;
    std::vector<std::pair<int, int>> m_friends;
};
int main()
{
    int nCase;
    std::vector<Class> classes;
    std::cin >> nCase;
    for (int i = 0; i < nCase; i++)
    {
        Class cls;
        std::cin >> cls;
        classes.emplace_back(cls);
    }
    for (auto cls : classes)
    {
        cls.Do();
    }
}