[프로그래머스] 자물쇠와 열쇠 (Java)

https://programmers.co.kr/learn/courses/30/lessons/60059?language=java 

코딩테스트 연습 - 자물쇠와 열쇠

import java.util.Arrays;

class Solution {
    int[][] map;
    int M, N;
    int mapSize;
    public boolean solution(int[][] key, int[][] lock) {
        boolean answer = false;
        M=key.length; 
        N=lock.length;
        mapSize=2*(M-1)+N;
        makeBoard(lock); 
        for (int d=0; d<4; d++){
            for (int y=0; y<M-1+N; y++){
                for (int x=0; x<M-1+N; x++){
                    if (move(y,x,key)){
                        answer=true;
                        return answer;
                    }
                }
            }
            rotate(key);
        }
        return answer;
    }
    
    public void makeBoard(int[][] lock){
        map=new int[mapSize][mapSize];
        for (int i=0; i<N; i++){
            for (int j=0; j<N; j++){
                map[i+M-1][j+M-1]=lock[i][j];
            }
        }
    }
    
    public boolean move(int y, int x, int[][] key){
        int[][] temp_map=new int[mapSize][mapSize];
        for (int i=0; i<mapSize; i++){
            temp_map[i]=Arrays.copyOf(map[i], mapSize);
        }
        for (int i=y; i<y+M; i++){
            for (int j=x; j<x+M; j++){
                temp_map[i][j]+=key[i-y][j-x];
            }
        }
        for (int i=M-1; i<M-1+N; i++){
            for (int j=M-1; j<M-1+N; j++){
                if (temp_map[i][j]!=1) return false;
            }
        }
        return true;
        
    }
    
    public void rotate(int[][] key){
        int[][] temp=new int[M][M];
        for (int j=0; j<M; j++){
            for (int i=0; i<M; i++){
                temp[j][i]=key[M-1-i][j];
            }
        }
        for (int i=0; i<M; i++) {
            key[i]=Arrays.copyOf(temp[i], M);
        }
    }
}

 

완전 어려웠던 완전탐색 문제..

이분(https://regularmember.tistory.com/186)의 코드를 참고하였다.(감사합니다bb)

key를 일단 크게 회전시키고.. 회전시킨 것에 대해 key를 y축,x축으로 0~M+N-1 평행이동 시켜줘야한다. 

쭉 평행이동 시켜주고 자물쇠 영역에 대해서 모든 원소가 1이면 true를 반환하는 형식이다.

 

여기서 포인트는.. [N+2*(M-1)][N+2*(M-1)]인 map을 잡아 평행이동을 해줘야 된다는 것이다.

평행이동 시킨 key와 map을 어떻게 연결할지도 고민을 많이 했다. 

평행이동 delta 값부터 시작해서 열쇠의 크기만큼 map 인덱스를 설정하고,

key는 map의 현재 인덱스에서 평행이동 delta를 뺀 값으로 설정하면 된다..

 

이문제는 다시 복습하는걸로..