자바알고리즘 - 구현 - 자물쇠와 열쇠

자바알고리즘 - 구현 - 자물쇠와 열쇠

 

문제

 

튜브는 열쇠로 자물쇠를 열고자한다.
자물쇠는 NXN크기의 정사각 격자형태고 열쇠는 MXM크기의 정사각 격자형태이다.
열쇠의 돌기와 자물쇠의 돌기가 만나서는 안되며 자물쇠의 모든 홈을 채워야지 열린다.
열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원배열 lock이 매개변수로 주어진다.
열쇠로 자물쇠를 열 수 있으면 true 없으면 false를 return하도록 하시오.
M은 3 ~ 20  N은 3 ~ 20   M은 N이하   key와 lock의 원소를 0과1이며 0은 홈부분 1은 돌기부분
O(N3)까지 가능할것으로보인다.

 

 

생각

 

key와 lock을 더했을때 원소가 모두 1이되면 다 채워진것이다.
key를 돌린다고 하였기 때문에 4번의 회전이 필요하다.
key는 lock의 범위 밖을 나가도된다.
그러므로 lock을 확대하여 처음부터 돌며 4번의 회전을 하며 모든원소의 합이 1이 되는 경우가 있는지를 확인한다.

이때 90도돌고 -> 확대된자물쇠 처음부터 끝까지 탐색 -> 다시 90도돌고 -> 확대된자물쇠 처음부터 끝까지 탐색을 반복한다.

 

 

 

 

코드

class Solution {
    //2.자물쇠의 0,0 부터시작하여 키를 4방향으로 돌리면서 확인해야하기때문에 90도씩 돌리는 함수가 필요하다.
    public static int[][] rotation(int[][] key) {
        int n = key.length;
        int m = key[0].length;
        int[][] new_key = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //90도를 돌려야한다.  //돌리면 열이 행이된다. //이때 역순으로 들어가기때문에 n(기존행) - i(현재행)-1을 해줘야 역순이된다. //0,0은 0,3이되고 1,0은 0,1이되고 2,2는 2,0이됨
                new_key[j][n - i - 1] = key[i][j];
            }
        }
        return new_key;
    }

    //3.키를 넣었을때 자물쇠가 전부다 1 인지 확인하는 부분이 필요하다.
    public static boolean check(int[][] big_lock) {
       // int n = big_lock.length;
        int ad_n = big_lock.length / 3;

        for (int i = ad_n; i < ad_n * 2; i++) {
            for (int j = ad_n; j < ad_n * 2; j++) {
                if (big_lock[i][j] != 1) {
                    return false;
                }
            }
        }
        return true;
    }


    public boolean solution(int[][] key, int[][] lock) {
        boolean answer = true;

        //1.키는 자물쇠의 범위를 벗어날수 있기 때문에 자물쇠를 3배늘려서 확인하는편이 낫다.
        int m = key.length;
        int n = lock.length;
        //자물쇠 3배확대
        int[][] big_lock = new int[n * 3][n * 3];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                big_lock[n + i][n + j] = lock[i][j];
            }
        }

        //4.키를 4방향씩 돌리며 자물쇠에 넣는다.
        for (int ro = 0; ro < 4; ro++) {
            key = rotation(key);


            //큰 자물쇠는 0,0에서 시작한다.
            for (int x = 0; x < n * 2; x++) {  // for( int j=0 ; j<N*3; j++) {   //키의 크기때문에 N*2까지만
                for (int y = 0; y < n * 2; y++) {  //  for(int k=0; k<N*3; k++) {

                    //자물쇠에 키를 넣어본다
                    for (int i = 0; i < m; i++) {
                        for (int j = 0; j < m; j++) {
                            big_lock[x+i][y + j] += key[i][j];  //자물쇠에 키의 원소값을 추가한다 = 넣는다. 이때 큰자물쇠의for문을 j<N*3을 해주면 범위가넘어간다.(키의범위도있기때문에)
                        }
                    }
                    //자물쇠가 다 1이라면 true인것이다.
                    if (check(big_lock)) {
                        return true;
                    }

                    //아니라면 자물쇠에서 키를 빼야한다.
                    for (int i = 0; i < m; i++) {
                        for (int j = 0; j < m; j++) {
                            big_lock[x+i][y+j] -= key[i][j];
                        }
                    }
                }
            }
        }
        return false;
    }
}

 

 

 

느낌

 

for문이 많아질때는 for문안에 변수를 신경써야한다. i++할것을 n++로 해서 삽질을 하였다!