10.자물쇠와 열쇠

📍 문제 설명

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

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

💡 접근

일단 key는 영역을 벗어나도 되니 lock의 범위를 넓혀서
key의 제일 아래부분과 lock의 제일 윗부분부터 맞춰가보도록 한다.
key인 M은 항상 lock인 N이하라고 했으니 같을 경우가 최대라고 생각해보면
NXN 이라면 N배만큼 큰 자물쇠를 만들어도 풀리는 문제였다.

 

처음과 끝까지 돌지 않기 위해 범위를 지정해놓고 돌리려했는데,

4X4로 그려서 보니 생각하는 범위가 아니여서 전체 범위를 탐색하였음

👩‍💻 코드

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);

        int[][] key = {{0,0,0},{1,0,0},{0,1,1}};
        int[][] lock = {{1,1,1},{1,1,0},{1,0,1}};
        boolean flag = false;

        int lockLen = lock.length;
        int keyLen = key.length;
        //열쇠로 자물쇠를 열어봐야하니 큰 수의 자물쇠를 만들기
        int[][] newLock = new int[lockLen*lockLen][lockLen*lockLen];
        int newLockLen = newLock.length;
        //가운데에 원본 자물쇠 넣기
        for(int i = 0; i < lockLen; i++) {
            for(int j = 0; j < lockLen; j++) {
                newLock[i+lockLen][j+lockLen] = lock[i][j];
            }
        }

        //M = 3 N = 3일 때 1,1에서 시작 7,7에서 끝
        //M = 2 N = 3일 때 2,2에서 시작 6,6에서 끝
        //M = 1 N = 3일 때 3,3에서 시작 5,5에서 끝

        //M = 4 N = 4일 때 3,3에서 시작 13,13에서 끝
        //M = 3 N = 4일 때 4,4에서 시작 12,12에서 끝
        //M = 2 N = 4일 때 5,5에서 시작 11,11에서 끝

        //시작은 n-m+1 끝은 n+m+1 -> 이거 아니다..

       //열쇠를 맞춰보기
        for(int i = 0; i < newLockLen; i++) {
            for(int j = 0; j < newLockLen; j++) {
                //4방향으로 모두 확인해본다.
                for(int rotation = 0; rotation < 4; rotation++) {
                    //key를 90도 회전 시키기
                    key = keyRotation90Degree(key);
                    //key의 크기만큼 열쇠를 맞춰본다.
                    for(int k = 0; k < keyLen; k++) {
                        for(int l = 0; l < keyLen; l++) {
                            //열쇠 돌기를 자물쇠의 홈 부분에 꽂는다.
                            if(k+i < newLockLen && l+j < newLockLen) newLock[k + i][l + j] += key[k][l];
                            }
                    }
                    //이 상태에서 모든 원소가 1인지(열리는지 확인해본다.)
                    if(check(newLock, lockLen)) flag = true;

                    for(int k = 0; k < keyLen; k++) {
                        for(int l = 0; l < keyLen; l++) {
                            //열쇠 돌기를 자물쇠의 홈 부분에서 다시뺀다.
                            if(k+i < newLockLen && l+j < newLockLen) newLock[k + i][l + j] -= key[k][l];
                        }
                    }
                }
            }
        }
    }

    //열쇠 90도 회전시키기
    private static int[][] keyRotation90Degree(int[][] key) {
        int n = key.length;
        int[][] rotationKey = new int[n][n];

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                rotationKey[j][n- i - 1] = key[i][j];
            }
        }
        return rotationKey;
    }

    //열쇠가 열리는지 확인
    private static boolean check(int[][] newLock, int n) {
        //다시 원본 배열의 크기로 변경
        int originLockLength = newLock.length / n;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n+n; j++) {
                if(newLock[i+n][j+n] != 1) return false;
            }
        }
        return true;
    }
}