프로그래머스 - 자물쇠와 열쇠

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 자물쇠와 열쇠

https://programmers.co.kr/learn/courses/30/lessons/60059

풀이 : lock의 크기를 3배로 늘려서 key의 위치를 대입시켜 조건을 체크

import java.util.*;
public class Solution {
    static boolean check = false;
 
    public boolean solution(int[][] key, int[][] lock) {
        int l = lock.length;
	int [][] arr = new int [3*l] [3*l];
	for(int i=0; i<l; i++) {
            for(int j=0; j<l; j++) {
            	arr[i+l][j+l] = lock[i][j];
            }
        }
		
		dfs(key, arr, 0);
        return check;
    }
    public void dfs(int[][]key, int [][] arr, int i) {
        int l = arr.length / 3;
	for (int a = l - key.length + 1; a < 2 * l; a++) {
		for (int b = l - key.length + 1; b < 2 * l; b++) {
			int [][] copy = Arrays.stream(arr).map(int[]::clone).toArray(int[][]::new); // 이중 배열 복사
			checkKey(key, copy, a, b); // key 체크
		}
	}
	if(check) return;
	if(i >= 4) return;
	int [][] temp = rotate(key); // 회전
	dfs(temp, arr, i+1);
    }
    
    public void checkKey(int[][] key, int[][] arr, int x, int y) {
        if(check) return;
	int l = arr.length / 3;
	for (int i = 0; i < key.length; i++) {
		for (int j = 0; j < key.length; j++) {
			arr[x + i][y + j]  += key[i][j];  
		}
	}		
    	boolean allCheck = true;
	for (int i = l; i < 2 * l; i++) {
		for (int j = l; j < 2 * l; j++) {
			if(arr[i][j] != 1) {
				allCheck = false;
				break;
			}
            }
		if(!allCheck) break;
	}
	if(allCheck) check = true;
    }
    
    public int[][] rotate(int [][] key) {
        int len = key.length;
        int[][] temp = new int[len][len];
        for(int i=0; i<len; i++) {
            for(int j=0; j<len; j++) {
                temp[i][j] = key[len-j-1][i];
            }
        }
		return temp;
    }
}