[Programmers] 자물쇠와 열쇠

문제

 

2020 KAKAO BLIND RECRUITMENT > 자물쇠와 열쇠

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

 

 

아이디어

 

이번 문제는 처음 접했을 땐 풀지 못하고 시간이 흘러 다시 접했을 때 풀게 된 문제였습니다.

 

풀이 방법은 단순히 회전을 하며 자물쇠를 열 수 있는 모든 경우를 찾는 완전탐색을 하면 되었습니다.

 

자물쇠는 고정 시키고 열쇠를 좌측 상단부터 우측 하단까지 옮기며 자물쇠를 열 수 있는지를 확인해주면 됩니다. 마치 2차원 배열을 탐색하는 것처럼요.

 

그림으로 나타내면 이런 모습이 나오겠습니다.

 

열쇠 움직이기

 

 

구현 코드 (Java)

 

class Solution {
    public boolean solution(int[][] key, int[][] lock) {
        for(int rotate=0; rotate<4; rotate++) { // 4번 회전
        	for(int i=-lock.length+1; i<lock.length; i++) { // key오른쪽 하단이 lock의 왼쪽 상단에 부딪히는 곳 부터 key, lock 조합 시작
        		for(int j=-lock.length+1; j<lock.length; j++) {
        			int temp[][] = new int[lock.length][lock.length]; // key와 lock이 합쳐진 배열 값, 모두 1이어야 자물쇠가 열리는 것을 의미
        			
        			for(int a=0; a<lock.length; a++) {
        				for(int b=0; b<lock.length; b++) {
        					temp[a][b] = lock[a][b]; // 자물쇠의 값을 저장
        				}
        			}
        			
        			for(int a=0; a<key.length; a++) {
        				for(int b=0; b<key.length; b++) {
        					if(a+i < lock.length && b+j < lock.length && a+i >= 0 && b+j >= 0) {
        						temp[a+i][b+j] = temp[a+i][b+j] + key[a][b]; // i, j만큼 벌어진 위치에 열쇠의 값을 저장
        					}
        				}
        			}
        			
        			boolean check = true;
        			temploop: for(int a=0; a<temp.length; a++) { // 자물쇠를 열 수 있는지 확인
        				for(int b=0; b<temp.length; b++) {
        					if(temp[a][b] != 1) {
        						check =false;
        						break temploop;
        					}
        				}
        			}
        			
        			if(check) {
        				return check;
        			}
        		}
        	}
        	
        	int newKey[][] = new int[key.length][key.length];
        	
        	for(int i=0; i<key.length; i++) { // 시계방향을 90도 회전
        		for(int j=0; j<key.length; j++) {
        			newKey[i][j] = key[j][key.length-1-i];
        		}
        	}
        	
        	for(int i=0; i<key.length; i++) {
        		for(int j=0; j<key.length; j++) {
        			key[i][j] = newKey[i][j];
        		}
        	}
        }
        
        return false;
    }
}

 

 

읽어주셔서 감사합니다.