ID : CLOCKSYNC 난이도 : 중 (재귀 완전탐색)

문제 : https://algospot.com/judge/problem/read/CLOCKSYNC

#include <iostream>
#include <vector>
 
 
class ClockSet
{
public:
    static const int SWITCHES = 10;        //스위치 개수
    static const int CLOCKS = 16;        //시계 개수
    const int INF = 987654321;
    int mMinCount;
 
 
    //mLinked[i][j] = 'x' : i번 스위치와 j번 시계가 연결되어있다.
    //mLinked[i][j] = '.' : i번 스위치와 j번 시계가 연결되어있지 않다.
    const char mLinked[SWITCHES][CLOCKS+1] = {
        "xxx.............",
        "...x...x.x.x....",
        "....x.....x...xx",
        "x...xxxx........",
        "......xxx.x.x...",
        "x.x...........xx",
        "...x..........xx",
        "....xx.x......xx",
        ".xxxxx..........",
        "...xxx...x...x.."
    };
 
    std::vector<int> mClockSet;
 
 
 
 
    void CountSwitch();
 
    //parClocks 현재 시계들의 상태
    //parSwitch 이번에 누를 스위치의 번호
    //가 주어질 때, 남은 스위치들을 눌러서 parClocks를 12시로 맞출 수 있는 최소 횟수를 반환한다.
    //만약 불가능하다면 INF 이상의 큰 수를 반환한다.
    int Solve(std::vector<int>& parClocks, int parSwitch);
 
private:
    //모든 시계가 12시를 가리키고 있는지 확인한다.
    bool _AreAligned(const std::vector<int>& parClocks);
    // parSwitch번 스위치를 누른다.
    void _Push(std::vector<int>& parClocks, int parSwtich);
    
};
 
 
int main()
{
    std::vector<ClockSet> clockList;
    int nTestCase;
 
 
    std::cin >> nTestCase;
    getchar();
 
    for (int i = 0; i < nTestCase; ++i)
    {
        ClockSet tmpClockSet;
        tmpClockSet.mClockSet.clear();
        for (int j = 0; j < 16; ++j)
        {
            int tmpTime;
            std::cin >> tmpTime;
            tmpClockSet.mClockSet.push_back(tmpTime);
        }
        getchar();
 
        clockList.push_back(tmpClockSet);
    }
 
 
    for (auto tmp : clockList)
    {
        tmp.CountSwitch();
        if (tmp.mMinCount == tmp.INF)
        {
            std::cout << -1 << std::endl;
        }
        else
        {
            std::cout << tmp.mMinCount << std::endl;
        }
    }
 
 
    return 0;
}
 
void ClockSet::CountSwitch()
{
 
    mMinCount = Solve(mClockSet, 0);
 
}
 
int ClockSet::Solve(std::vector<int>& parClocks, int parSwitch)
{
    if (parSwitch == SWITCHES)
    {
        return _AreAligned(parClocks) ? 0 : INF;
    }
    //이 스위치를 0번 누르는 경우부터 세 번 누르는 경우까지를 모두 시도한다.
    int ret = INF;
    for (int cnt = 0; cnt < 4; ++cnt)
    {
        int tmpRet = cnt + Solve(parClocks, parSwitch + 1);
        if (ret > tmpRet)
        {
            ret = tmpRet;
        }
        _Push(parClocks, parSwitch);
    }
 
    return ret;
}
 
bool ClockSet::_AreAligned(const std::vector<int>& parClocks)
{
    for (auto clock : parClocks)
    {
        if (clock != 12)
            return false;
    }
    return true;
}
 
void ClockSet::_Push(std::vector<int>& parClocks, int parSwtich)
{
    for (int clock = 0; clock < CLOCKS; ++clock)
    {
        if (mLinked[parSwtich][clock] == 'x')
        {
            parClocks[clock] += 3;
            if (parClocks[clock] == 15)
            {
                parClocks[clock] = 3;
            }
        }
    }
}