[완전탐색] 시계 맞추기(문제 ID:CLOCKSYNC, 난이도:중)

1. 문제정의

그림과 같이 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 (<= 30) 가 주어진다.
각 테스트 케이스는 한 줄에 16개의 정수로 주어지며, 각 정수는 0번부터 15번까지 각 시계가 가리키고 있는 시간을 12, 3, 6, 9 중 하나로 표현한다.

출력

각 테스트 케이스당 한 줄을 출력한다. 시계들을 모두 12시로 돌려놓기 위해 눌러야 할 스위치의 최소 수를 출력한다. 만약 이것이 불가능할 경우 -1 을 출력한다.

---

2. 문제 설계

완전 탐색을 이용해 모든 경우의 수를 알아보는 것입니다. 재귀 호출을 이용해 코드를 만들어 봅시다.

부분 문제 정의각 스위치는 0, 1, 2, 3번으로 구분할 수 있다. (4번 누른 것은 0번 누른 것과 같음)그래서 0번 스위치를 시작으로 각 스위치가 0~3번 누른 경우를 모두 조사하여 최솟값을 반환한다.

---

3. 구현

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 9999;
const int SWITCH = 10;
const int CLOCKS = 16;

//linked[i][j]=1 i번 스위치와 j번 시계가 연결되어 있다
//linked[i][j]=0 i번 스위치와 j번 시계가 연결되어 있지 않다
const char linked[SWITCH][CLOCKS] = {
        {'x', 'x', 'x', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', 'x', '.', '.', '.', 'x', '.', 'x', '.', 'x', '.', '.', '.', '.'},
        {'.', '.', '.', '.', 'x', '.', '.', '.', '.', '.', 'x', '.', '.', '.', 'x', 'x'},
        {'x', '.', '.', '.', 'x', 'x', 'x', 'x', '.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', 'x', 'x', 'x', '.', 'x', '.', 'x', '.', '.', '.'},
        {'x', '.', 'x', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', 'x', 'x'},
        {'.', '.', '.', 'x', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', 'x', 'x'},
        {'.', '.', '.', '.', 'x', 'x', '.', 'x', '.', '.', '.', '.', '.', '.', 'x', 'x'},
        {'.', 'x', 'x', 'x', 'x', 'x', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', 'x', 'x', 'x', '.', '.', '.', 'x', '.', '.', '.', 'x', '.', '.'}
};

//모든 시계가 12시를 가리키고 있는지 확인
bool areAligned(const vector<int> & clocks){
   for (int i = 0; i < CLOCKS; i++)
               if (clocks[i] != 12)
                       return false;
        return true;
}

//switch번 스위치를 누른다 모든시계 3시간씩 증가
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;
               }
}

//clocks:현재 시계들의 상태
//swtch:이번에 누를 스위치의 번호
//가 주어질 때, 남은 스위치들을 눌러서 clocks를 12시로 맞출 수 있는 최소 횟수를 반환
//만약 불가능하다면 INF 이상의 큰 수를 반환
int solve(vector<int> &clocks, int swtch){
  //Base Case : 모든 시계가 12시를 가리키면 종료
        if (swtch == SWITCH)
               return areAligned(clocks) ? 0 : INF;

        //이 스위치를 0번 누르는 경우부터 세번 누르는 경우까지를 모두 시도 
  //4번 누르는 것은 0번과 같음
        int result = INF;
        for (int cnt = 0; cnt < 4; cnt++) {
               result = min(result, cnt + solve(clocks, swtch + 1));
               push(clocks, swtch);
        }

        //push(clocks, swtch)가 네번 호출되었으니 clocks는 원래와 같은 상태
        return result;
}

int main(void){
        int testCase;
        vector<int> clocks(CLOCKS);
        cin >> testCase;
        if (testCase < 0)
               return 0;

        for (int i = 0; i < testCase; i++){
               for (int j = 0; j < CLOCKS; j++)
                       cin >> clocks[j];
 
               int result = solve(clocks, 0);
      
               if ( result == INF) cout << -1 << endl;
               else cout << result << endl;
        }
        return 0;
}

---

4. 테스트

 

 

출처 : https://algospot.com/judge/problem/read/CLOCKSYNC