[프로그래머스][구현][Java] 자물쇠와 열쇠 : Lv 3.

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/60059

1. 문제 핵심

이 문제는 M x M 크기의 열쇠와 N x N 크기의 자물쇠가 주어졌을 때, 열쇠를 회전하고 이동시켜 자물쇠를 열 수 있는지 확인하는 문제다.

조건은 다음과 같다.

1. key는 90도씩 회전할 수 있다.
2. key는 상하좌우로 이동할 수 있다.
3. lock 영역 밖의 key는 영향을 주지 않는다.
4. lock의 모든 홈(0)은 key의 돌기(1)로 채워져야 한다.
5. lock의 돌기(1)와 key의 돌기(1)가 겹치면 안 된다.

 

즉, 자물쇠 영역 안에서는 최종적으로 모든 칸이 1이 되어야 한다.

 

2. 풀이 아이디어

처음에는 key의 돌기 좌표만 따로 저장해서 회전과 이동을 처리하려고 생각할 수 있다.

하지만 그렇게 하면 다음 조건을 직접 모두 검사해야 한다.

- key의 돌기가 lock의 홈을 채웠는가?
- key의 돌기와 lock의 돌기가 충돌하지 않았는가?
- lock의 모든 홈이 채워졌는가?
- lock 바깥으로 나간 key는 무시했는가?

 

이 조건을 좌표만으로 관리하면 생각보다 복잡해진다.

그래서 이 문제는 확장된 board를 만들고, 그 중앙에 lock을 배치한 뒤 key를 모든 위치에 올려보는 방식이 더 직관적이다.

 

3. 왜 확장 board를 사용하는가?

문제에서 key는 lock 밖으로 나가도 된다. 즉, 배열의 범위를 벗어난 키는 무시하는 것이다!

그런데 lock 배열만 가지고 계산하면 key가 바깥으로 나갈 때 음수 좌표가 생긴다. (-1, 0) (0, -1) 와 같은 좌표는 배열에서 사용할 수 없다.

그래서 아예 lock 주변에 여백을 둔 큰 board를 만드는 것이다 !

int size = 2 * m + n;
int[][] board = new int[size][size];

 

여기서 m은 key의 크기, n은 lock의 크기다.

[ key 여백 ][ lock ][ key 여백 ]

 

우선 lock은 board 중앙에 배치한다.

board[m + i][m + j] = lock[i][j];

즉, lock 영역은 board에서 다음 범위에 위치한다.

행: m ~ m + n - 1
열: m ~ m + n - 1

 

 

그 다음, key를 board 위에 올릴 때는 값을 더한다.

board[x + i][y + j] += key[i][j];

 

이때 lock 영역 안에서 가능한 경우는 다음과 같다.

0	1	1	홈을 채움
1	0	1	기존 돌기 유지
0	0	0	홈이 안 채워짐
1	1	2	돌기끼리 충돌

따라서 lock 영역의 모든 값이 정확히 1이면 자물쇠가 열린다.

0이면 -> 홈이 안 채워진 상태, 2이면 -> 돌기끼리 충돌한 상태 이므로, 

if (board[i][j] != 1) {
	return false;
}

 1이 아니면 열 수 없는 걸로 간주할 수 있다!

 

 

4. 코드 풀이

import java.util.*;
class Solution {
    public boolean solution(int[][] key, int[][] lock) {
        int m = key.length;
        int n = lock.length;
        
        int size = 2*m + n; // board 크기
        int[][] board = new int[size][size];
        
        for(int i =0 ; i < n; i++){
            for(int j = 0; j < n; j++){
                board[m + i][m + j] = lock[i][j];
            }
        }
        
        for(int r = 0; r < 4; r++){
            
            for(int i = 0; i <= size-m; i++){
                for(int j = 0; j <= size-m; j++){
                    putKey(board, key, i, j);
                    
                    if(checkFit(board, m, n))
                        return true;
                    
                    removeKey(board, key, i, j);
                }
            }
            
            key = turnRight(key);
            
        }
        
        
        
        return false;
    }
    
    public boolean checkFit(int[][] board, int m, int n){
        for(int i = m ; i < m+n; i++){
            for(int j = m; j < m+n; j++){
                if(board[i][j] != 1){
                    return false;
                }
            }
        }
        
        return true;
    }
    
    public void putKey(int[][] board, int[][] key, int x, int y){
        for(int i = 0; i <key.length; i++){
            for(int j = 0; j < key.length; j++){
                board[x+i][y+j] += key[i][j];
            }
        }
    }
    
    public void removeKey(int[][] board, int[][] key, int x, int y){
        for(int i = 0; i <key.length; i++){
            for(int j = 0; j < key.length; j++){
                board[x+i][y+j] -= key[i][j];
            }
        }
    }
    
    public int[][] turnRight(int[][] key){
        int m = key.length;
        int[][] newKey = new int[m][m];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                newKey[j][m-1-i] = key[i][j];
            }
        }
        
        return newKey;
    }
}