[종만북][알고스팟] CLOCKSYNC(시계 맞추기) - 완전탐색(BruteForce) + 그리디(Greedy) JAVA

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

algospot.com :: CLOCKSYNC

코드설명

완전탐색 + 그리디 문제입니다.

 

그리디 태그를 붙인 이유는, 시계는 12시간이 지나면 제 자리로 돌아오기에 하나의 스위치를 4번 이상 누를 일은 절대 없습니다. 또한, 스위치를 누르는 순서는 전혀 중요하지 않습니다. 두 스위치를 누르는 순서를 바꾼다고 해서 그 결과가 바뀌지 않기 때문입니다.따라서 우리가 계산해야할 것은 각 스위치를 몇번이냐 누를 것이냐 뿐입니다.(조합을 사용할 것 입니다.)

 

이렇게 문제를 단순화시켜도, 완전 탐색을 곧장 적용할 수는 없습니다. 완전 탐색 알고리즘을 사용하려면 스위치를 누르는 횟수의 모든 조합을 하나하나 열거할 수 있어야하는데, 각 스위치를 몇번 누르는지는 상관 없고 따라서 그 조합의 수는 무한합니다. 

 

시계는 12시간이 지나면 제자리로 돌아온다는 점을 이용하면 무한한 조합의 수를 유한하게 바꿀 수 있습니다. 어떤 스위치를 네번 누르면 연결된 시계는 모두 12시간씩 앞으로 이동하니 하나도 누르지 않은 것과 다름이 없습니다. 따라서 어떤 스위치 건 간에 최대 세번 이상 누를 일이 없다는 것을 알게 됩니다. 따라서 각 스위치를 누르는 횟수는 0에서 3 사이의 정수입니다. 열 개의 스위치가 있으니 전체 경우의 수는 4^10 = 2^20 = 1,048,576 개 (약 백만개)입니다. 재귀호출의 깊이가 정해져있기 때문에 10준 for문과 다르지 않지만, 재귀로 구현합니다. 

 

답의 상한은 16개의 스위치를 모두 3번씩 누르는 경우이므로 3*16 + 1 로 49 입니다. .

 

유의해야할점은,

1. 이 문제 역시 재귀형태로 스위치의 최소 클릭수를 반환합니다.

void 타입으로 진행하지 않기에 더 깔끔합니다.

 

2. 앞에 말했듯 시계는 12시간이 지나면 제자리로 돌아온다는 점을 고려합니다.

 

3. 코드 2를 보면 단순히 실행순서를 바꿈으로써 엄청나게 효율적으로 재귀를 줄일 수 있었습니다.

처음에 제가 작성했던 코드는 아래와 같습니다.

//4번하면 원래대로 돌아옵니다.
for(int i=0; i<=4; i++) {
    if(i != 0) clickSwitch(level, clock); //시계를 돌리는 함수(스위치의 인덱스를 전달할 것임)
    ret = Math.min(ret, clockSync(level + 1, clock) + i);
}

총 4번의 반복문을 돕니다. 이유는 첫번째(i==0)에는 회전하지 않음을 표현하고, 나머지부터는 i==1, i==2, i==3, i==4로해서 결국 원래의 모양으로 돌아오는 것을 표현합니다.

 

위의 코드와 다른점은, clickSwitch를 누르기전에 미리 재귀가 실행되어 위의 코드와 다르게 함수 실행횟수가 1번 줄어든다는 점입니다. 재귀의 level이 총 10까지 depth가 있기에 이러한 1번은 엄청난 시간을 줄일 수 있습니다.

//4번하면 원래대로 돌아옵니다.
for(int i=0; i<=3; i++) {
    ret = Math.min(ret, clockSync(level + 1, clock) + i);
    clickSwitch(level, clock); //시계를 돌리는 함수(스위치의 인덱스를 전달할 것임)
}

이와 같이 단순히 순서를 바꿈으로써 약 5000ms(5초)의 시간이 줄어들었습니다.

 

또, 이 문제 같은경우 왜 3번이 아닌 4번을 회전시켜야하는지 궁금할 수 있습니다. 

이유는, 상위재귀가 하위재귀를 호출했을떄 해당 하위재귀종료 후 다른 하위재귀2를 실행하기 위해서는 이전 상태에서 같이 시작하여야 하기 때문입니다. 

 

일반적으로 storeClock[][]과 같이 이전 상태를 저장해서 사용하는데, 그렇게 할경우 매번 해당 상태를 저장하여야 합니다. 총 4번이 돌아오면 다시 해당 상태로 돌아온다는 것을 알게된다면, 코드의 속도를 획기적으로 줄일 수 있습니다.

코드

package algorhythm;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int INF = 9999, SWITCHES = 10, CLOCKS = 16;
	public static int answer = 0;
	// linked[i][j] = 'x' : i번 스위치와 j번 시계가 연결되어 있다.
	// linked[i][j] = '.' : i번 스위치와 j번 시계가 연결되어 있지 않다.
	//[switches][Clocks+1]
	public static String[] linked= {
	// 0123456789012345
			"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.."
	};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		while(C-- > 0) {
			st = new StringTokenizer(br.readLine());
			int[] clock = new int[16];
			for(int i=0;i<16;i++) {
				clock[i] = Integer.parseInt(st.nextToken());
			}
			answer = solve(clock, 0);
			System.out.println(answer == INF ? -1 : answer);
		}
		
	}
	//모든 시계가 12시를 가리키고 있는지 확인한다.
	public static boolean areAligned(int[] clocks) {
		for(int i=0;i<16;i++) {
			if(clocks[i] != 12) return false;
		}
		return true;
	}
	
	//swtch 번 스위치를 누른다.
	public static void push(int[] clocks, int swtch) {
		for(int clock = 0; clock<CLOCKS;clock++) {
			if(linked[swtch].charAt(clock) == 'x') {
				clocks[clock] += 3;
				if(clocks[clock] == 15) clocks[clock] = 3;
			}
		}
	}
	
	// clocks: 현재 시계들의 상태
	// switch : 이번에 누를 스위치의 번호
	// 가 주어질때, 남은 스위치들을 눌러서 clocks를 12시로 맞출 수 있는 최소 횟수를 반환한다.
	// 만약 불가능하다면 INF 이상의 큰 수를 반환한다.
	public static int solve(int[] clocks, int swtch) {
		if(swtch == SWITCHES) return areAligned(clocks) ? 0 : INF;
		
		//이 스위치를 0번 누르는 경우부터 세번 누르는 경우까지를 모두 시도한다.
		int ret = INF;
		for(int cnt=0;cnt<4;cnt++) {
			//이 스위치를 0번 누르는 경우부터 세번 누르는 경우까지를 모두 시도한다.
			ret = Math.min(ret,  cnt + solve(clocks, swtch + 1) );
			push(clocks, swtch);
		}
		//push(clocks, swtch)가 네번 호출되었으니 clocks는 원래와 같은 상태가 된다.
		return ret;
	}
	
}

 

코드 2 (시간이 오래걸리는 코드입니다.) 코드3에서 정말 간단히 함수의 순서를 바꿈으로써 약 5000ms를 줄였습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M, H, W;
	public static int answer = 0;
	public static int[] clock;
	public static int[][] switchArr = new int[][] 
	{ //[10][16]개.
		{1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0},
		{0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,1},
		{1,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,1,1,1,0,1,0,1,0,0,0},
		{1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1},
		{0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1},
		{0,0,0,0,1,1,0,1,0,0,0,0,0,0,1,1},
		{0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,1,1,1,0,0,0,1,0,0,0,1,0,0}
	};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		clock = new int[16];
		while(C-- > 0) {
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<16;i++) {
				clock[i] = Integer.parseInt(st.nextToken());
			}
			answer = clockSync(0, clock);
			if(answer == 16*3 + 1) {
				System.out.println(-1);
			}else {
				System.out.println(answer);
			}
		}
	}
	
	//스위치를 누르는 경우. 4^10개의 경우의 수가 발생합니다.
	public static int clockSync(int level, int[] clock) {
		if(level == 10) {
			//성공한 경우입니다.
			if(isAllTwelve(clock) == true) {
				return 0;
			}
			//실패한 경우입니다. 답의 상한을 반환함으로써 처리합니다.
			else {
				return 16*3 + 1; // 16 * 3 + 1
			}
		}
		
		int ret = Integer.MAX_VALUE;
		//4번하면 원래대로 돌아오므로 안해도 될듯
		for(int i=0; i<=4; i++) {
			if(i != 0) clickSwitch(level, clock); //시계를 돌리는 함수(스위치의 인덱스를 전달할 것임)
			ret = Math.min(ret, clockSync(level + 1, clock) + i);
		}
		
		return ret;
	}
	
	public static boolean clickSwitch(int idx, int[] clock) {
		for(int j=0; j<switchArr[idx].length;j++) {
			if(switchArr[idx][j] == 1) {
				clock[j] += 3;
				if(clock[j] > 12) clock[j] = 3;
			}
		}
		return true;
	}
	
	public static boolean isAllTwelve(int[] clock) {
		for(int i=0;i<16;i++) {
			if(clock[i] != 12) {
				return false;
			}
		}
		return true;
	}
	
}

 

코드 3(시간이 줄어든 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M, H, W;
	public static int answer = 0;
	public static int[] clock;
	public static int[][] switchArr = new int[][] 
	{ //[10][16]개.
		{1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0},
		{0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,1},
		{1,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,1,1,1,0,1,0,1,0,0,0},
		{1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1},
		{0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1},
		{0,0,0,0,1,1,0,1,0,0,0,0,0,0,1,1},
		{0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,1,1,1,0,0,0,1,0,0,0,1,0,0}
	};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		clock = new int[16];
		while(C-- > 0) {
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<16;i++) {
				clock[i] = Integer.parseInt(st.nextToken());
			}
			answer = clockSync(0, clock);
			if(answer == 16*3 + 1) {
				System.out.println(-1);
			}else {
				System.out.println(answer);
			}
		}
	}
	
	//스위치를 누르는 경우. 4^10개의 경우의 수가 발생합니다.
	public static int clockSync(int level, int[] clock) {
		if(level == 10) {
			//성공한 경우입니다.
			if(isAllTwelve(clock) == true) {
				return 0;
			}
			//실패한 경우입니다. 답의 상한을 반환함으로써 처리합니다.
			else {
				return 16*3 + 1; // 16 * 3 + 1
			}
		}
		
		int ret = Integer.MAX_VALUE;
		for(int i=0; i<=3; i++) {
			ret = Math.min(ret, clockSync(level + 1, clock) + i);
			clickSwitch(level, clock); //시계를 돌리는 함수(스위치의 인덱스를 전달할 것임)
		}
		
		return ret;
	}
	
	public static boolean clickSwitch(int idx, int[] clock) {
		for(int j=0; j<switchArr[idx].length;j++) {
			if(switchArr[idx][j] == 1) {
				clock[j] += 3;
				if(clock[j] > 12) clock[j] = 3;
			}
		}
		return true;
	}
	
	public static boolean isAllTwelve(int[] clock) {
		for(int i=0;i<16;i++) {
			if(clock[i] != 12) {
				return false;
			}
		}
		return true;
	}
	
}