풀이 )
0번 스위치를 시작으로 15번 스위치까지 각각 4번씩 눌러가면서 재귀호출을 통해서 모든 경우의 수에 대해서 탐색한다.
전체 경우의 수가 4^10(≒10^6)이므로 시간초과가 나지 않는다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> push[10] = {
{0, 1, 2},
{3, 7, 9, 11},
{4, 10, 14, 15},
{0, 4, 5, 6, 7},
{6, 7, 8, 10, 12},
{0, 2, 14, 15},
{3, 14, 15},
{4, 5, 7, 14, 15},
{1, 2, 3, 4, 5},
{3, 4, 5, 9, 13}
};
int clocks[16];
int dfs(int num){
if(num == 10){
for(int i = 0; i < 16; ++i){
if(clocks[i] != 12)
return 1e7;
}
return 0;
}
int ret = 1e7;
for(int i = 0; i < 4; ++i){
ret = min(ret, i+dfs(num+1));
int len = push[num].size();
for(int i = 0; i < len; ++i){
clocks[push[num][i]] = clocks[push[num][i]]%12+3;
}
}
return ret;
}
int main(void){
int c;
cin >> c;
while(c--){
for(int i = 0; i < 16; ++i)
cin >> clocks[i];
int ans = dfs(0);
if(ans >= 1e7)
ans = -1;
cout << ans << '\n';
}
}
'문제풀이 > 알고스팟' 카테고리의 다른 글
[C++] 알고스팟 - BOARDCOVER (0) | 2020.12.28 |
---|---|
[C++] 알고스팟 - PICNIC (0) | 2020.11.01 |
[C++] 알고스팟 - FESTIVAL (0) | 2020.03.09 |