[Algorithm Strategies] 05. Exhaustive Search - Clock Sync

1. Exhaustive Search

1.1 Clock Sync - Optimization Problem

1.1.1 Problem

- 4 X 4 격자 형태로 배치된 열어섯 개의 시계가 존재, 이 시계들은 12시, 3시, 6시, 9시를 가리키고 있음

   - 이 시계들을 모두 12시를 가리키도록 변경, 시간을 조작하는 유일한 방법은 열개의 스위치들을 조작하는 것

     - 각 스위치들은 모두 적게는 세 개에서 많게는 다섯 개의 시계에 연결

       - 한 스위치를 누를 때 마다 해당 스위치와 연결된 시계들의 시간은 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

 - 첫 줄에 테스트 케이스 개수가 주어지고, 각 테스트 케이스는 한 줄에 16개의 정수로 주어짐

   - 각 정수는 0번부터 15번까지 각 시계가 가리키고 있는 시간을 12, 3, 6, 9중 하나로 표현

/* Input*/
2
12 6 6 6 6 6 12 12 12 12 12 12 12 12 12 12
12 9 3 12 6 6 6 9 3 12 9 12 9 12 12 6 6

/* Output */
2
9

1.1.2 Algorithm Strategy

- 시계는 12시간이 지나면 제 자리로 돌아온다는 점을 이용하면 무한한 조합의 수를 유한하게 변경 가능

   - 어떤 스위치를 최대 세번 이상 누를 일은 존재X

 - 2차원 벡터를 생성하여 스위치와 연결되어 있는 시계를 생성

vector<vector<int>> ConnectedSwitch;

 - 시계를 스위치에 의해 변경되는 것은 함수로 따로 설정하여 생성

   - 이후 재귀 함수를 통해 시계가 모두 12시로 향하게 만드는 함수 생성하여 문제를 풂

void Exhaustive::ChangeClock(vector<int>& clock, int sch);

1.1.3 implementation

1.1.3.1 Main Function

 - 메인 함수에서 입력을 따로 받지 않고 넣는 방식을 사용

vector<int> clock {12, 6, 6, 6, 6, 6, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12};
//vector<int> clock {12, 9, 3, 12, 6, 6, 9, 3, 12, 9, 12, 9, 12, 12, 6, 6};
cout << exhaustive.ClockSync(clock, 0) << endl;

1.1.3.2 Change Clock

 - 시계와 스위치를 전달받아 스위치에 해당하는 시계들을 찾아 값 변경

for (int i = 0; i < ConnectedSwitch[sch].size(); i++)
{
    clock[ConnectedSwitch[sch][i]] += 3;
    if (clock[ConnectedSwitch[sch][i]] == 15) clock[ConnectedSwitch[sch][i]] = 3;
}

1.1.3.2 Clock Sync

int Exhaustive::ClockSync(vector<int>& clock, int sch);

 - 마지막인 10번인 스위치가 3번 눌렸을 때 시계가 12시를 바라보지 않을 경우 무한대의 값 반환

if (sch == 10) return areAligned(clock) ? 0 : INTMAX;

   - 스위치를 0번 누르는 경우의 수 부터 3번 누르는 경우의 수까지 모두 시도

     - 4번을 누를 경우 원래 자리로 돌아옴

       - 즉 0번 부터 9번까지를 스위치 3번을 누르면서 모든 경우의 수를 추출

int ret = INTMAX;
for (int i = 0; i < 4; i++)
{
    ret = min(ret, i + ClockSync(clock, sch + 1)); ChangeClock(clock, sch);
}
return ret;