[알고스팟] 시계 맞추기 (완전탐색과 최적화)

링크:https://www.algospot.com/judge/problem/read/CLOCKSYNC

algospot.com :: CLOCKSYNC

---

 완전탐색은 가능한 모든 사건을 탐색하는 알고리즘입니다. 모든 것을 탐색한다는 워딩부터 왠지 계산이 힘들 것 같습니다. 그러나 많은 경우에 그렇지만, 항상 그런 것은 아닙니다. 입력 자료가 많지 않을 경우 오히려 더 빠를 수도 있으며, 처음에 문제에 접근하기 위한 좋은 직관을 제공하기도 합니다.

 특히 최적화 문제의 경우 완전탐색이 유용할 수 있습니다. 최적화 문제는 단순히 하나의 답을 도출하는 것이 아닌, 다수의 답 중 최적의 해를 구하는 문제를 말합니다. 완전탐색은 최적화를 위한 가장 기초적인 접근법이라는 점에서 눈여겨볼 필요가 있습니다. 따라서 여기서는 알고스팟의 시계 맞추기 문제를 이용하여 완전탐색에 익숙해져보려고 합니다. 

 간단하게 구현할 경우 중첩 반복문을 이용하여 구현할 수 있겠으나, 재귀 함수를 이용하면 더 효과적으로 구현할 수 있습니다. 소스코드는 파이썬 버전과 C++ 버전이 있습니다.

<Python3.8 소스 코드>

switchs = [
    [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]
  ]

def get_minimum_click(clocks, switch):
    if switch == len(switchs):
        ret = 0 if all(map(lambda x: x == 12, clocks)) else 1e9
        return ret

    mini = 1e9
    for cnt in range(4):
        mini = min(mini, cnt + get_minimum_click(clocks, switch + 1))
        for clock_idx in switchs[switch]:
            clocks[clock_idx] += 3
            if clocks[clock_idx] == 15: clocks[clock_idx] = 3

    return mini


for _ in sys.stdin.readline():
    clocks = list(map(int, sys.stdin.readline()))
    print(get_minimum_click(clocks, 0))

get_minimum_click 함수가 직접 완전탐색을 수행하는 재귀함수입니다. 풀이에 들어가기 전 몇 가지 직관이 중요합니다.

 우선 이 문제의 풀이에 있어 시계를 누르는 순서는 전혀 중요하지 않습니다. 각각의 스위치는 시계를 3시간 단위로만 움직인다고 했으므로 4번을 누르면 시계는 원래 모양으로 돌아오게 되기 때문입니다. 따라서 스위치에 인덱스를 부여하여 순서대로 탐색하되, 스위치를 4번 누르는 경우의 수를 각각 분기하여 최적의 해를 구하면 답이 됩니다.

 완전 탐색의 구현에 있어서 중요한 것은 기저 사례의 설정과 부분문제 설정입니다. 코드의 초반부에서는 기저사례를 설정하고 있습니다. 스위치를 순서대로 탐색한다고 했으므로, 모든 스위치를 탐색하고 인덱스가 범위를 벗어났을 때 시계의 정렬 상태(모든 시계가 12시)를 확인하는 것으로 해주었습니다. 만약 정렬이 되어있다면 0을 반환하여 지금까지 구한 최소값을 반환할 것이며, 정렬이 되어 있지 않다면 큰 수를 반환하여 갱신을 막습니다.

 그 아래의 부분이 부분문제를 해결하고 있습니다. mini 변수가 부분문제가 반환하는 최소값이자, 최종적으로 반환할 결과를 의미합니다. min함수 내에서 재귀적으로 호출되는 get_minimum_click함수는 본인 스택의 최소값을 반환할 것이고, 스택 최하단부에서는 mini가 최종 결과를 반환할 것입니다. 앞서 언급했듯이 스위치를 4번 누르면 최초 상태로 돌아가므로 0, 1, 2, 3번 누르는 경우만 각각 고려해주면 되겠습니다.

 

<C++ 소스 코드>

#include <vector>
#include <cstdio>
#include <algorithm>


vector<vector<int>> switchs = {
	{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}
};

bool isAligned(const vector<int>& clocks)
{
	for (int clock : clocks)
		if (clock != 12)
			return false;
	return true;
}

int getMinimumCount(vector<int>& clocks, int switchIdx=0)
{
	int numSwitch = static_cast<int>(switchs.size());
	if (switchIdx == numSwitch)
		return isAligned(clocks) ? 0 : 1e9;

	int mini = 1e9;
	for (int cnt = 0; cnt < 4; cnt++)
	{
		mini = min(mini, cnt + getMinimumCount(clocks, switchIdx + 1));
		for (int idx: switchs.at(switchIdx))
		{
			clocks[idx] += 3;
			if (clocks[idx] == 15) clocks[idx] = 3;
		}
	}
	return mini;
}

int main(void)
{
	int numTestcase;
	int numClocks = 16;

	scanf("%d", &numTestcase);
	for (int i = 0; i < numTestcase; i++)
	{
		vector<int> clocks;
		for (int j = 0; j < numClocks; j++)
		{
			int tmp;
			scanf("%d", &tmp);
			clocks.push_back(tmp);
		}

		printf("%d\n", getMinimumCount(clocks));
	}
}

C++ 코드는 정렬상태를 확인하는 isAligned 함수를 따로 구현한 것 외에는 큰 차이가 없으므로 설명을 생략하도록 하겠습니다.