[pro] 프로그래머스 level3 60059 자물쇠와 열쇠 (Java) - 시뮬레이션

[문제]

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

프로그래머스

 

[풀이]

이 문제의 핵심은 lock의 좌표를 확장해야 한다는 것...!

lock 배열의 크기를 벗어나게 자물쇠를 채워도 된다. 따라서 lock의 좌표가 다음 그림과 같이 확장 가능하다.

lock.length + (key.length-1)*2

 

 

원래의 lock을 새로 만든 new lock에 옮긴 다음, 회전을 시켜가며 key로 자물쇠를 채울 수 있는지 확인한다.

key로 자물쇠를 채울 수 있는지는 위의 그림에서 초록색 key를 이동시켜가며 key의 배열 부분만큼 lock의 배열에 더해줬을 때 실제 lock의 부분인 파란색 사각형이 모두 1(돌기를 의미)로 바뀌어있으면 된다. 1이 아니라면 그대로 홈(0)이거나 돌기와 돌기가 만난 것을 의미하므로 key를 다시 이동시켜서 확인하도록 한다.

 

퍼즐 조각 채우기 가 생각난 문제...?

 

[코드]

 

import java.util.*;

class Solution {
    public boolean solution(int[][] key, int[][] lock) {
        boolean answer = false;
        //열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return
        
        //lock을 확장함
        int len = lock.length + key.length*2 - 2;
        int[][] nl = new int[len][len];
        for(int i=key.length-1; i<key.length+lock.length-1; i++){
            for(int j=key.length-1; j<key.length+lock.length-1; j++){
                nl[i][j] = lock[i-key.length+1][j-key.length+1];
            }
        }
        
        //회전시킴
        for(int i=0; i<4; i++){
            if(match(key, nl, lock.length)){
                answer = true;
                break;
            }
            else{
                //key 회전시키기
                rotate(key);
            }
        }
        
        return answer;
    }
    
    public boolean match(int[][] key, int[][] lock, int len){
        for(int i=0; i<key.length+len-1; i++){
            for(int j=0; j<key.length+len-1; j++){ //이동
                //new lock + key
                for(int x=0; x<key.length; x++){
                    for(int y=0; y<key.length; y++){
                        lock[i+x][j+y] += key[x][y];
                    }
                }
                
                //lock이 전부 1이 되었는지 확인 - 홈이 모두 채워졌는지 + 돌기와 돌기가 만나지 않았는지
                boolean check = true;
                for(int x=key.length-1; x<key.length+len-1; x++){
                    for(int y=key.length-1; y<key.length+len-1; y++){
                        if(lock[x][y]!=1){
                            check = false;
                            break;
                        }
                    }
                }
                
                if(check){
                    return true;
                }
                
                //lock 원상복구. lock - key
                for(int x=0; x<key.length; x++){
                    for(int y=0; y<key.length; y++){
                        lock[i+x][j+y] -= key[x][y];
                    }
                }
                
            }
        }
        return false;
    }
    
    public void rotate(int[][] key){
        int[][] temp = new int[key.length][key.length];
        for(int i=0; i<key.length; i++){
            for(int j=0; j<key.length; j++){
                temp[i][j] = key[j][key.length-i-1];
            }
        }
        
        for(int i=0; i<key.length; i++){
            for(int j=0; j<key.length; j++){
                key[i][j] = temp[i][j];
            }
        }
    }
}