[Programmars] 자물쇠와 열쇠

문제

• Programmars 60059
• 문제의 저작권은 Programmars에 있습니다.

접근방식

1.먼저 다음과 같이 M=3, N=4인 key와 lock이 있다고 가정한다.

2.key를 lock위에서 이동시키면서 lock의 홈을 채울수 있는지 확인해야한다. 그런데 key가 lock의 좌표 밖을 벗어나도 되므로 key가 갈 수 있는 범위를 다음과 같이 확장시킬 수 있다.

3.확장시키면 원래의 lock.length 에서 가로,세로에 (key.length-1)*2한 만큼의 범위를 갈 수 있다. 따라서 길이가 (key.length-1)*2인 map배열을 만들고 여기에 기존의 lock좌표를 표시해준다. 그리고 map위에서 key를 이동시키면서 lock범위 안에 있는 인덱스를 key의 값과 비교해주면서 홈을 채우는지 체크한다.

1. 순서를 정리하면 key 를 90도씩 회전시키고 나온 모양대로 위의 2,3과정을 진행하면 된다. 90도 회전 후 인덱스를 구하는 방법은 다음과 같이 그려서 간단한 점화식을 구할 수 있다.
   

public static boolean solution(int[][] key, int[][] lock) {
		int[][] map = new int[lock.length + 2 * (key.length - 1)][lock.length + 2 * (key.length - 1)]; // lock 확장
		int lockCnt = 0; // lock의 홈 개수
		int cnt;

		for (int[] m : map) Arrays.fill(m, -1); //lock범위가 아닌 부분 -1표시

		// 1. 확장한 lock(map)에 lock을 넣는다.
		for (int i = 0; i < lock.length; i++) {
			for (int j = 0; j < lock.length; j++) {
				map[i + key.length - 1][j + key.length - 1] = lock[i][j];
				if (lock[i][j] == 0) lockCnt++;
			}
		}

		// 2. key를 시계방향 회전한다(처음 생략)
		for (int d = 0; d < 4; d++) {
			// 3. key를 돌면서 map안의 lock좌표와 비교한다.
			for (int i = 0; i < map.length - key.length + 1; i++) {
				for (int j = 0; j < map.length - key.length + 1; j++) {
					cnt = 0; // 일치하는 개수

					for (int k = 0; k < key.length; k++) {
						for (int l = 0; l < key.length; l++) {
							// lock의 범위 안에 있는지 체크		
							if(map[i+k][j+l] == -1) continue;

							// key의 돌기와 lock의 돌기가 만나는지 체크
							if (map[i + k][j + l] == 1 && key[k][l] == 1) cnt--;

							// key의 돌기와 lock의 홈이 만나는지 체크
							if (map[i + k][j + l] == 0 && key[k][l] == 1) cnt++;
						}
					}

					if (cnt == lockCnt) return true;
				}
			}
			
			if( d == 3 ) break; //240도 모두 회전했으므로 종료
			key = rotate(key);
		}

		return false;
	}

	private static int[][] rotate(int[][] key) {
		int[][] arr = new int[key.length][key.length];

		for (int i = 0; i < key.length; i++) {
			for (int j = 0; j < key.length; j++) {
				arr[j][key.length - 1 - i] = key[i][j];
			}
		}
		return arr;
	}