[Java] 프로그래머스 - 자물쇠와 열쇠

[문제]

[풀이]

열쇠가 튀어나온 부분과, 잠금장치의 파인부분 좌표만 각각 저장한 후, 아래와 같은 방식으로 가능한 모든 열쇠의 위치를 옮겨가며 탐색하였지만 시간초과로 실패하였습니다.

위 : x, y - 1
오른쪽 : x + 1, y
왼쪽 : x - 1, y
아래 : x, y + 1
90*회전 : y,x

 

따라서 해당 블로그를 참고하여 풀이를 진행하였습니다.

https://jellyinghead.tistory.com/28

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

자물쇠의 크기를 n에서 n+2*(m-1)로 확장하여 새로운 배열 extended[][] 을 만들어 열쇠를 배열의 모든 위치에 올려서 찾아보면 되는 거였습니다. 

확장된 자물쇠 배열

- moveKey()를 통해 가능한 모든 열쇠를 꽂아보며 탐색합니다.

- unLock()을 통해 자물쇠에 키를 정확히 꽂을수 있는지 확인합니다. 이때, 만약 1을 가진 모든 키의 값이 실제 자물쇠의 좌표인

(m-1 ~ N-m, m-1~N-m)에 위치한다면 자물쇠에 꽂힌것으로 간주하고 cnt++를 실행합니다.

- 만약, 자물쇠의 파인 개수 hole == cnt 라면 자물쇠는 풀렸다고 간주합니다.

 

 

[코드]

import java.util.*;
class Solution {
    public static int n;
    public static int m;
    public static int N;
    public static int extened[][]; // 확장된 lock
    public static int hole = 0;
    public boolean solution(int[][] key, int[][] lock) {
        boolean answer = true;
        n = lock.length;
        m = key.length;
        N = n + 2*(m-1);
        extened = new int[N][N];
        extend(lock);
        answer = moveKey(key);
        return answer;
    }
    public static void extend(int[][] lock) {
        for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
                if(lock[i][j] == 0) {
                    hole++;
                }
				extened[m-1+i][m-1+j] = lock[i][j];   
            }
		}
		// for(int i = 0; i < N; i++) {
		// 	for(int j = 0; j < N; j++) {
		// System.out.print(extened[i][j] + " ");
		// }
		// System.out.println();
		// }
		// System.out.println(hole);
    }
    public static boolean moveKey(int[][] key) {
		for(int i = 0; i <= N-m; i++) {
			for(int j = 0; j <= N-m; j++) {
                //자물쇠에 키를 꽂음
                if(unLock(key,i,j)){
                    return true;
                }
			}
		}
        for(int k=0;k<3;k++) {
            key = rotate(key);
            for(int i = 0; i <= N-m; i++) {
                for(int j = 0; j <= N-m; j++) {
                    //자물쇠에 키를 꽂음
                    if(unLock(key,i,j)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public static boolean unLock(int[][] key, int i, int j) {
        int cnt = 0;
        for(int x = 0; x < m; x++) {
			for(int y = 0; y < m; y++) {
				if(extened[i+x][j+y] == 1 && key[x][y] == 1) {
                    return false;
                }
				else if(extened[i+x][j+y] == 0 && key[x][y] == 1) {
                    if(m-1 <= x+i && x+i <= N-m && m-1 <= y+j && y+j <= N-m) {
                        cnt++;
                    }
                }
			}
		}
        if(cnt == hole) {
            return true;
        }
        return false;
    }
    public static int[][] rotate(int key[][]) {
		int len = key.length;
		int convert[][] = new int[len][len];

		for(int i = 0; i < len; i++) {
			for(int j = 0; j < len; j++) {
				convert[j][len-i-1] = key[i][j];
			}
		}

		return convert;
	}
}