시계 맞추기
문제 : https://algospot.com/judge/problem/read/CLOCKSYNC
문제
그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다.
시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다. 스위치들과 그들이 연결된 시계들의 목록은 다음과 같다.
| 0 | 0, 1, 2 |
| 1 | 3, 7, 9, 11 |
| 2 | 4, 10, 14, 15 |
| 3 | 0, 4, 5, 6, 7 |
| 4 | 6, 7, 8, 10, 12 |
| 5 | 0, 2, 14, 15 |
| 6 | 3, 14, 15 |
| 7 | 4, 5, 7, 14, 15 |
| 8 | 1, 2, 3, 4, 5 |
| 9 | 3, 4, 5, 9, 13 |
시계들은 맨 윗줄부터, 왼쪽에서 오른쪽으로 순서대로 번호가 매겨졌다고 가정하자. 시계들이 현재 가리키는 시간들이 주어졌을 때, 모든 시계를 12시로 돌리기 위해 최소한 눌러야 할 스위치의 수를 계산하는 프로그램을 작성하시오.
코드 ( C ++ ) 종만북 참고
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const int INF = 9999, SWITCHES = 10, CLOCKS = 16;
// linked[i][j] = 'x' : i번 스위치와 j번 시계가 연결되어 있다.
// linked[i][j] = '.' : i번 스위치와 j번 시계가 연결되어 있지 않다.
const char linked[10][16 + 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.." };
// 모든 시계가 12시 방향인지 확인
bool areAligned(const vector<int>& clocks)
{
for (int i = 0; i < CLOCKS; ++i)
if (clocks[i] != 12)
return false;
return true;
}
// swtch번 스위치를 누름
void push(vector<int>& clocks, int swtch) {
for (int i = 0; i < CLOCKS; ++i)
{
if (linked[swtch][i] == 'x') {
clocks[i] += 3;
if (clocks[i] == 15) clocks[i] = 3;
}
}
}
// clocks: 현재 시계 상태
// swtch: 이번에 누를 스위치의 번호
// 남은 스위치들을 눌러 clocks를 12시로 맞출 수 있는 최소 횟수를 반환한다.
// 불가능시 INF 이상의 큰 수를 반환한다.
int solve(vector<int>& clocks, int swtch)
{
if (swtch == SWITCHES) return areAligned(clocks) ? 0 : INF;
int ret = INF;
for (int i = 0; i < 4; ++i) {
ret = min(ret, solve(clocks, swtch + 1) + i);
push(clocks, swtch);
}
return ret;
}
int main()
{
int C;
cin >> C;
while (C--) {
vector<int> clocks;
for (int i = 0; i < 16; ++i)
{
int n;
cin >> n;
clocks.push_back(n);
}
int ans = solve(clocks, 0);
if (ans != INF)
cout << ans << "\n";
else
cout << -1 << "\n";
}
}
