6.8문제: 시계 맞추기(ID: CLOCKSYNC)
문제
그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다.
시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다. 스위치들과 그들이 연결된 시계들의 목록은 다음과 같다.
| 스위치 번호 | 연결된 시계들 | 스위치 번호 | 연결된 시계들 |
|---|---|---|---|
| 0 | 0, 1, 2 | 5 | 0, 2, 14, 15 |
| 1 | 3, 7, 9, 11 | 6 | 3, 14, 15 |
| 2 | 4, 10, 14, 15 | 7 | 4, 5, 7, 14, 15 |
| 3 | 0, 4, 5, 6, 7 | 8 | 1, 2, 3, 4, 5 |
| 4 | 6, 7, 8, 10, 12 | 9 | 3, 4, 5, 9, 13 |
시계들은 맨 윗줄부터, 왼쪽에서 오른쪽으로 순서대로 번호가 매겨졌다고 가정하자. 시계들이 현재 가리키는 시간들이 주어졌을 때, 모든 시계를 12시로 돌리기 위해 최소한 눌러야 할 스위치의 수를 계산하는 프로그램을 작성하시오.
입력
첫 줄에 테스트 케이스의 개수 C (<= 30) 가 주어진다.
각 테스트 케이스는 한 줄에 16개의 정수로 주어지며, 각 정수는 0번부터 15번까지 각 시계가 가리키고 있는 시간을 12, 3, 6, 9 중 하나로 표현한다.출력
각 테스트 케이스당 한 줄을 출력한다. 시계들을 모두 12시로 돌려놓기 위해 눌러야 할 스위치의 최소 수를 출력한다. 만약 이것이 불가능할 경우 -1 을 출력한다.
예제 입력
2 12 6 6 6 6 6 12 12 12 12 12 12 12 12 12 12 12 9 3 12 6 6 9 3 12 9 12 9 12 12 6 6예제 출력
2 9
First Thoughts
"스위치와 시계의 관계"
각 스위치와 연결된 시계표를 보고 어떻게 해야할지 고민했다. 먼저 vector형의 스위치번호에 따라 연결되있는 시계들의 번호만 나열하려고 하였다. 근데 차후에 해당되는 시계에 모두 3을 더해줘야된다는 점과 시계번호만 나열했을 때 순회하며 더하는 작업이 어려울거라 판단되어 앞 6.5게임판 덮기 문제와 유사하게 배열을 생성하였다.
My code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define MAX_NUM 1048576;
using namespace std;
int link_switch[10][16] = { {3,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,3,0,0,0,3,0,3,0,3,0,0,0,0},{0,0,0,0,3,0,0,0,0,0,3,0,0,0,3,3},{3,0,0,0,3,3,3,3,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,3,3,3,0,3,0,3,0,0,0},{3,0,3,0,0,0,0,0,0,0,0,0,0,0,3,3},{0,0,0,3,0,0,0,0,0,0,0,0,0,0,3,3},{0,0,0,0,3,3,0,3,0,0,0,0,0,0,3,3}, {0,3,3,3,3,3,0,0,0,0,0,0,0,0,0,0},{0,0,0,3,3,3,0,0,0,3,0,0,0,3,0,0}};
void next(int clock[], int type) {
for (int i = 0; i < 16; i++) {
clock[i]+=link_switch[type][i];
if (clock[i] == 15) {
clock[i] = 3;
}
}
}
int search(int clock[],int type) {
int i,j;
int res = MAX_NUM;
bool all = true;
if (type == 10) {
for (i = 0; i < 16; i++) {
if (clock[i] != 12) {
all = false;
break;
}
}
if (all == false) {
return MAX_NUM;
}
else {
return 0;
}
}
for (i = 0; i < 4; i++) {
res = min(res, i + search(clock,type+1));
next(clock, type);
}
return res;
}
int main(void) {
int C;
int i,j;
int w;
int clock[16];
cin >> C;
for (i = 0; i < C; i++) {
memset(clock, 0, sizeof(clock));
for (j = 0; j < 16; j++) {
cin >> clock[j];
}
w = search(clock,0);
if (w == 1048576) {
cout << -1 << endl;
}
else {
cout << w << endl;
}
}
}Answer code
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 9999, SWITCHES = 10, CLOCKS = 16;
const char linked[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.."
};
bool areAligned(const vector<int>& clocks) {
for (int i = 0; i < 16;i++) {
if (clocks[i] != 12) {
return false;
}
}
return true;
}
void push(vector<int>& clocks, int swtch) {
for (int clock = 0; clock < CLOCKS; ++clock) {
if (linked[swtch][clock] == 'x') {
clocks[clock] += 3;
if (clocks[clock] == 15)
clocks[clock] = 3;
}
}
}
int solve(vector<int>& clocks, int swtch) {
if (swtch == SWITCHES) {
return areAligned(clocks) ? 0 : INF;
}
int ret = INF;
for (int cnt = 0; cnt < 4; ++cnt) {
ret = min(ret, cnt + solve(clocks, swtch + 1));
push(clocks, swtch);
}
return ret;
}
int main(void) {
int C;
int w;
int time;
vector<int> clocks;
cin >> C;
for (int i = 0; i < C; i++) {
for (int j = 0; j < 16; j++) {
cin >> time;
clocks.push_back(time);
}
w=solve(clocks, 0);
if (w == INF) {
cout << -1 << endl;
}
else {
cout << w << endl;
}
clocks.clear();
}
}Difference & Faults
"스위치를 누를 수 있는 최대 횟수"
어느 스위치든지 총 네 번을 누르면 다시 제자리로 돌아온다. 이점을 생각하지 못하여 책의 아이디어를 차용하여 코드로 구현하였다. 여기서 최대 경우의 수인 4의 10제곱(1048576을 최대 숫자)로 설정할 수 있었다.
Impressions
"문제의 특성 파악"
어떤 문제든 그 문제의 특성을 잘 파악하고 그 특성을 활용하면 코드를 좀 더 쉽고 간결하게 작성할 수 있는 거 같다. 이 문제의 가장 큰 특징은 시계라는 사물을 이용한 점과 연결된 스위치 사이의 관계성이다. 특히 실생활 속 문제들은 어느 사물이나 상황의 특징성을 파악하고 고려한다면 코드를 작성하는데 도움이 되는 거 같다.
Summary
이 문제는 그래도 다른 문제들에 비해 쉽게 풀렸던 문제인거 같다. 정말 핵심적인 그 시계와 스위치의 특성을 아주 잘 활용한다면 코드의 구현도 예외 처리도 비교적 수월했다. 6장을 마무리하며 느낀 것은 모든 문제들이 재귀적 특성을 잘 활용하며 함수로 구현하였다. 특히 게이판 덮기 문제와 시계 맞추기 문제에서 원래 상태로 복귀하는 것을 재귀함수로 구현한 것이 매우 신기하였다. 아직까지도 부족한 점이 많지만 6장의 모든 문제들이 어느 맥락에서 비슷하고 "무식하게 풀기"의 정의를 느낌적으로 이해한거 같다.
