[프로그래머스] 자물쇠와 열쇠::알고리즘

열쇠를 회전하고, 이동시켜 자물쇠를 열 수 있는지 확인하는 알고리즘

 

열쇠의 크기(M)는 자물쇠의 크기(N) 보다 작을 수 있고,

 

열쇠가 자물쇠의 범위를 벗어나도 맞물리기만 하면 되므로

 

M - 1 + N + M - 1 = N + (M - 1) * 2 크기의 이차원 배열을 새로 만들어 줍니다.

 

가운데 N 자리에 lock을 복사합니다.

 

이차원 배열을 계속해서 복사하고, 복사된 이차원 배열에 열쇠가 한 칸씩 이동하면서

 

이차원 배열과 열쇠를 더해 lock 자리가 있는 곳만 모두 1인지 확인하여 true를 반환합니다.

 

 

Java 코드

 

public class Solution_자물쇠와열쇠 {
	
	public static boolean solution(int[][] key, int[][] lock) {
		int M = key.length;
		int N = lock.length;
		int MN = N + (M - 1) * 2;
		int[][] map = new int[MN][MN];
		
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j)
				map[M - 1 + i][M - 1 + j] = lock[i][j];
		}
		
		for (int r = 0; r < 4; ++r) {
			for (int i = 0; i <= MN - M; ++i) {
				loop:for (int j = 0; j <= MN - M; ++j) {
					int[][] copy = new int[MN][MN];
					
					for (int k = 0; k < MN; ++k) {
						for (int l = 0; l < MN; ++l)
							copy[k][l] = map[k][l];
					}
					
					for (int k = 0; k < M; ++k) {
						for (int l = 0; l < M; ++l)
							copy[i+k][j+l] += key[k][l];
					}
					
					for (int k = 0; k < N; ++k) {
						for (int l = 0; l < N; ++l) {
							if (copy[M - 1 + k][M - 1 + l] != 1)
								continue loop;
						}
					}
					
					return true;
				}
			}
			
			for (int i = 0; i < M / 2; ++i) {
				int len = M - 1 - i * 2;
				int last = M - 1 - i;
				int[] temp = new int[len];
				
				for (int j = 0; j < len; ++j) {
					temp[j] = key[i][i + j];
					key[i][i + j] = key[i + j][last];
					key[i + j][last] = key[last][last-j];
					key[last][last-j] = key[last-j][i];
					key[last-j][i] = temp[j];
				}
			}
		}
		
		return false;
	}
	
	public static void main(String[] args) {
		System.out.println(solution(
				new int[][] { {0, 0, 0}, {1, 0, 0}, {0, 1, 1} },
				new int[][] { {1, 1, 1}, {1, 1, 0}, {1, 0, 1} }
		));
	}

}