문제

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

그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다.

시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다. 스위치들과 그들이 연결된 시계들의 목록은 다음과 같다.

시계들은 맨 윗줄부터, 왼쪽에서 오른쪽으로 순서대로 번호가 매겨졌다고 가정하자. 시계들이 현재 가리키는 시간들이 주어졌을 때, 모든 시계를 12시로 돌리기 위해 최소한 눌러야 할 스위치의 수를 계산하는 프로그램을 작성하시오.

풀이(나의 풀이)

이 문제도 앞서 풀었던 문제들과 마찬가지로 완전 탐색으로 접근하여 풀이를 시도하였다. 주어진 시계들에 대해 10개의 스위치를 누르는 과정을 반복하여 풀려고 시도하였는데, 문제는 앞서 풀었던 문제들과 달리 여러 가지의 경우의 수 중 가장 좋은 답을 찾아야 하기 때문에 풀이과정에 있어서 어려움을 겪었다.

먼저 앞 문제들의 방식대로 재귀 메소드를 다음과 같이 설계하였다.

1. 모든 버튼들에 대해 반복문으로 순회하여 특정 버튼을 눌러 시간들을 더한다.

2. 현재 기록된 누른 횟수를 재귀 메소드를 호출하여 리턴받은 누른 횟수와 비교하여 작은 값을 누른 횟수로 갱신한다.

3. 눌렀던 버튼을 다시 누르기 전 상태로 되돌려 시계들을 이전 값으로 되돌린다.

4. 반복문이 종료된 후 기록된 누른 횟수를 리턴한다.

5. 메소드의 초반부에 모든 시계가 정렬되었는지 검사하여 정렬되었을 경우 기저사례로 1을 리턴한다.

내 풀이의 문제점

이 방식대로 문제를 풀려고 시도하니, 오버플로가 발생하거나 제대로 된 값을 리턴하지 못했다. 따라서 책을 참고하여 문제를 다시 풀어본 결과, 위 방식에서 다음과 같은 문제점이 발견되었다.

1) 모든 시계를 정렬하는데 눌러야 하는 버튼 횟수의 최솟값을 비교하는 데 최솟값의 비교에 있어서 알고리즘이 유효하지 않다.

2) 버튼들을 조합하여도 정렬할 수 없는 경우, 즉 정렬이 불가능한 경우 재귀를 탈출하여 임의의 값을 리턴하여야 하는데, 해당 경우를 판별할 수 없다.

1번의 경우 앞서 모든 경우의 수를 계산하는 문제들의 풀이대로 접근하려고 하여 재귀 메소드에서 최적의 답을 찾도록 구현하지 못하였다. 특히 재귀메소드에서 매개변수로 전달되는 변수의 특성을 고려하여 메소드를 설계하여야 했는데, 이러한 부분이 부족했다.

2번의 경우 문제의 특성을 정확히 파악하지 못하여 풀이에 있어서 비효율적인 코드를 사용하였다. 버튼을 누를 때마다 시계의 시간이 3시간씩 더해지는데, 총 4번 누를 경우 원래 상태로 복귀하게 된다. 즉, 버튼을 누르는 최소 경우에서는 한 버튼을 4번 이상 누를 필요가 없으며 4번 이상 누르게 될 경우 풀이가 불가능한 경우를 의미한다.

즉, 본 문제는 모든 경우를 세는 앞서 풀었던 문제들과 달리 최적의 답을 도출하는 최적화 문제에 해당된다. 따라서 최적화 문제를 풀 수 있도록 알고리즘을 설계하여야 한다.

풀이(책 참고)

따라서 책의 풀이를 참고하여 다음과 같이 코드를 작성하였다.

static int cycle(int[] n, int sch) {
		int ret = 99999999;
		if (sch == 10) {
			if (isAligned(n))
				return 0;
			else
				return ret;
		}
		for (int j = 0; j < 4; j++) {
			ret = Math.min(ret, j + cycle(n, sch + 1));
			int[] arr = clock.get(sch);
            // 스위치를 눌러서 3시간씩 더하는 부분
			for (int k : arr) {
				n[k] += 3;
				if (n[k] == 15)
					n[k] = 3;
			}
		}

		return ret;

	}

재귀 메소드의 매개변수로 각 시계들의 시간이 기록된 배열 n과 이번에 누를 스위치 번호 sch를 설정하였다. 내가 시도한 풀이에서는 매개변수로 각각의 버튼이 눌린 횟수를 기록하여 전달하도록 구현하였는데, 버튼은 4번 이상 누를 필요가 없으므로(시계의 시간이 원래의 상태로 되돌아오므로) 이를 기록하지 않고, 재귀 메소드 내에서 특정 버튼에 대해 3번까지 반복하여 버튼을 누르도록 구현하였다. 이 때, 반복문을 돌 때마다 해당 버튼을 누르는 횟수가 1씩 증가하므로, 반복 횟수를 기록하는 변수 ret은 재귀 메소드의 리턴값에 스위치를 반복한 횟수를 더한 값 중 최소값으로 기록된다.

이 때 호출되는 재귀 메소드의 매개 변수인 스위치 번호는 1을 더한 값으로 호출하여 다음 버튼을 누른 횟수를 계산하도록 한다. 따라서 재귀함수가 호출될 때마다 다음 번호를 누르도록 호출되며, 최종적으로 10개의 스위치를 최대 3번씩 누른 후 스위치번호가 10이 되었을 때, 기저사례로 정렬된 경우 0을 리턴하고, 그렇지 않은 경우 정렬이 불가능한 케이스이므로 매우 큰 값 99999999를 리턴하도록 한다.

완전탐색에서 기저사례로 1을 출력한 경우와 달리 0을 리턴하는 이유는 앞서 문제들은 정렬, 배치 등 특정 작업의 경우의 수를 계산하므로 각각의 경우를 1회로 보기 때문에 기저사례로 1을 리턴하지만, 본 문제의 경우 가장 최소가 되는 반복 횟수를 리턴해야 하므로, 함수 호출의 최종부에 정렬에 성공하였을 때 0을 리턴하고, 빠져나오면서 각 버튼을 눌렀던 횟수를 더하여 최저값을 비교하여야 하므로 0을 리턴해야 한다.

결과적으로 봤을 때 해당 재귀함수는 각각의 버튼들을 눌러보는 10중 for문의 형태로 풀이될 수 있다. 즉, 완전탐색 알고리즘의 경우 중첩된 반복문을 재귀함수를 통해 효율적인 코드로 풀어내어 답을 도출하는 과정으로 볼 수 있다.