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

문제

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

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

 

접근법

저번에 풀었던 적이 있는데도 다시 풀기가 어려웠다.

저번에는 dfs를 통해서 배열을 90도로 돌렸는데 이번엔 순수 포문만을 사용했다.

열쇠의 모든 부분이 자물쇠와 겹쳐야 하는 것이 아니고 상하좌우로 움직여서 열쇠의 일부분만을 결합시킬 수도 있다.

따라서 열쇠와 자물쇠가 모두 들어갈 수 있는 큰 배열을 만들고 열쇠를 삽입하며 가능성을 확인한다.

solution 메소드에선 배열을 90도로 돌리고, 배열이 90도로 돌아간 상태에서 열쇠를 자물쇠에 삽입하는 모든 경우의 수를 계산한다.

isPossible 메소드에서는 이중 포문을 통해 모든 경우의 수를 계산한다.

check 메소드에선 자물쇠와 열쇠가 맞는지는 판단한다.

 

코드

class Solution {
    public boolean solution(int[][] key, int[][] lock) {

        for(int i=0;i<4;i++){
            //키를 90도 돌리고
            key = rotate(key);
            //가능한지 여부를 판단
            if(isPossible(key, lock))
                return true;
        }

        return false;
    }

    private boolean isPossible(int[][] key, int[][] lock) {
        //열쇠와 자물쇠가 들어갈 수 있는 큰 배열을 만들고
        int[][] copy = new int[lock.length + key.length * 2][lock.length + key.length * 2];

	    //큰 배열의 가운데에 자물쇠의 값들을 넣어준다.
        for(int i=0; i<lock.length;i++){
            for(int j=0;j<lock.length; j++){
                copy[i+key.length][j+key.length] = lock[i][j];
            }
        }

	    //큰 배열을 모두 돌면서 열쇠와 자물쇠가 결합할 수 있는지를 판단한다.
        for(int i=0;i<copy.length-key.length;i++){
            for(int j=0;j<copy.length-key.length;j++){
                if(check(i, j, key, copy))
                    return true;
            }
        }

        return false;
    }

    private boolean check(int x, int y, int[][] key, int[][] copy) {
        int[][] arr = new int[copy.length][copy.length];

	    //열쇠를 자물쇠에 넣다 뺐다가를 반복하기 위해 arr 배열에 복사해준다.
        for(int i=0;i<arr.length;i++){
            arr[i] = copy[i].clone();
        }

	    //반복문을 돌면서 key의 값이 1이면 arr 배열의 key 자리에 +1을 해준다.
        //+1을 해주는 이유는 열쇠의 홈과 자물쇠의 홈이 만나면 그 가능성은 불가능하기 때문
        for(int i=0;i<key.length;i++){
            for(int j=0;j<key.length;j++){
                if(key[i][j] == 1)
                    arr[i+x][j+y]++;
            }
        }

	    //자물쇠 부분을 확인하며 자물쇠 배열 부분이 모두 1이 되면 성공 하나라도 1이 아니면 실패
        for(int i=key.length;i<arr.length-key.length;i++){
            for(int j=key.length;j<arr.length-key.length;j++){
                if(arr[i][j] != 1)
                    return false;
            }
        }

        return true;
    }

	//배열을 90도 돌리는 메소드
    private int[][] rotate(int[][] key){
        int copy[][] = new int[key.length][key.length];

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