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

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

프로그래머스

 

코딩테스트 연습 > 2020 KAKAO BLIND RECRUITMENT > 자물쇠와 열쇠

문제 설명

고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.
잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.
자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
M은 항상 N 이하입니다.
key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
0은 홈 부분, 1은 돌기 부분을 나타냅니다.

 

문제 접근

제일 사람들이 어렵다고 생각하는 구현(시뮬레이션) 문제이다. 
이런 문제를 보면 제일 먼저 하는 일은 항상 매개변수로 넘어온 값들을 static으로 즉 클래스 변수로 바꿔서 다른 메서드에서도 활용 가능하게 바꾼다. static 변수가 아니라면 매번 매개변수로 넘겨줘야 해서 상당히 불편하다. 

먼저 자물쇠의 빈칸의 개수(채워줘야 하는 칸 개수)를  count 하고 Lock이라는 클래스 2차원 배열에 복사를 해주었다.

문제를 읽어보면 key(열쇠)는 회전이 가능하고 동서남북으로 이동이 가능하다고 나와있다.
나는 먼저  회전을 시키고 이동하는 방식으로 문제를 풀었다.

 

copy 2차원 배열에 처음 매개변수로 들어온 2차원 배열을 복사하고 4번 for문을 돌렸다.

처음 i == 0 이면 회전 시키지 않고 바로 check(검사) 메서드로 넘겨주었다.

나머지 i == 1 ~ 3은 회전 시키는데 중요 포인트는 회전 시킨 값을 다시 회전 시키는 것이다.

해당 코드 : copy = rotate(copy); 

rotate 메서드는 설명을 생략하겠다. 

 

자 이제 제일 중요한 check 메서드를 설명하겠다. check 메서드는 회전을 시킨 2차원 key 배열 받아서 

이동시키고 확인하는 메서드이다.

 

어떤 방식으로 이동하고 확인을 할 것인지? 고민하는 게 참 어려웠다.

문제의 입출력 예

[1, 1, 1]                               
[1, 1, 0]
[1, 0, 1]

자물쇠 (고정)

[0, 0, 0]                               
[1, 0, 0]
[0, 1, 1]

키 : rotate x 

 

먼저 list에 키 좌표들을 int[] 배열로 넣는다. 

list : [1, 0] , [2, 1] , [2, 2]

 

자물쇠에서 0인 부분을 채워야 한다. 어떤 case가 있을까? 
먼저 자물쇠의 [1, 2]를 채운다고 해보자. 

 

 

 

이렇게 3가지 case가 나온다. 

 key 리스트 [1, 0] , [2, 1] , [2, 2]

[1, 0] 기준으로 자물쇠의 [1,2]에 들어가는 상황 

[2, 1] 기준으로 자물쇠의 [1,2]에 들어가는 상황

[2, 2] 기준으로 자물쇠의 [1,2]에 들어가는 상황 

 

전부 불가능한 케이스이다. 

이걸 계속 반복한다. 

 

 

1번 회전하고 찾는 상황 자물쇠의 빈칸을 모두 채우고 이미 채워진 공간은 건드리지 않았으니 true이다.

 

91점 코드

import java.util.*;

class Solution {
    static int m, n;
    static int [] arx = {-1,1,0,0};
    static int [] ary = {0,0,-1,1};
    static int count;
    static int [][] Lock;
    public boolean solution(int[][] key, int[][] lock) {
        m = key.length;
        n = lock.length;
        
        Lock = new int [n][n];
        
        // 빈칸 개수
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(lock[i][j] == 0) count++;
                Lock[i][j] = lock[i][j];
            }
        }
        
        int [][] copy = new int [m][m];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                copy[i][j] = key[i][j];
            }
        }
        for(int i = 0; i < 4; i++){
            if(i != 0){
                copy = rotate(copy);
            }
            if(check(copy)) return true;
        }
           
        return false;
    }
    public static int [][] rotate(int [][] cur){
        int [][] temp = new int [m][m];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                temp[i][j] = cur[m-1-j][i];
            }
        }
        return temp;
    }
      
    public static boolean validation(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx < n && ny < n) return true;
        return false;
    }
    
    public static boolean check(int [][] input){
        ArrayList<int [] > list = new ArrayList<>(); 
        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                 if(input[i][j] == 1){
                     list.add(new int [] {i,j});
                 }
            } 
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(Lock[i][j] == 1) continue;
                for(int [] target : list){ // 기준
                    int x = target[0];
                    int y = target[1];
                    int sum = 1;
                    boolean flag = true;
                    for(int [] same : list){
                        int next_x = same[0] - x;
                        int next_y = same[1] - y;
                        if(next_x == 0 && next_y == 0) continue;
                        int check_x = i + next_x;
                        int check_y = j + next_y;
                        if(!validation(check_x, check_y)) continue;
                        if(Lock[check_x][check_y] == 1){
                            flag = false;
                            break;
                        }
                        else sum++;
                    }
                    if(flag && sum == count){
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

 

 

반례

처음부터 자물쇠의 홈이 모두 채워져 있는 상황을 생각하지 못하였다.

자물쇠의 빈칸 개수 즉 count = 0 이면 바로 true로 리턴하면 끝이다. 

해당 코드를 추가 했더니 100점이 나왔다.

100점 코드

import java.util.*;

class Solution {
    static int m, n;
    static int [] arx = {-1,1,0,0};
    static int [] ary = {0,0,-1,1};
    static int count;
    static int [][] Lock;
    public boolean solution(int[][] key, int[][] lock) {
        m = key.length;
        n = lock.length;
        
        Lock = new int [n][n];
        
        // 빈칸 개수
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(lock[i][j] == 0) count++;
                Lock[i][j] = lock[i][j];
            }
        }
        
        if(count == 0) return true;
        
        int [][] copy = new int [m][m];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                copy[i][j] = key[i][j];
            }
        }
        for(int i = 0; i < 4; i++){
            if(i != 0){
                copy = rotate(copy);
            }
            if(check(copy)) return true;
        }
           
        return false;
    }
    public static int [][] rotate(int [][] cur){
        int [][] temp = new int [m][m];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                temp[i][j] = cur[m-1-j][i];
            }
        }
        return temp;
    }
      
    public static boolean validation(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx < n && ny < n) return true;
        return false;
    }
    
    public static boolean check(int [][] input){
        ArrayList<int [] > list = new ArrayList<>(); 
        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                 if(input[i][j] == 1){
                     list.add(new int [] {i,j});
                 }
            } 
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(Lock[i][j] == 1) continue;
                for(int [] target : list){ // 기준
                    int x = target[0];
                    int y = target[1];
                    int sum = 1;
                    boolean flag = true;
                    for(int [] same : list){
                        int next_x = same[0] - x;
                        int next_y = same[1] - y;
                        if(next_x == 0 && next_y == 0) continue;
                        int check_x = i + next_x;
                        int check_y = j + next_y;
                        if(!validation(check_x, check_y)) continue;
                        if(Lock[check_x][check_y] == 1){
                            flag = false;
                            break;
                        }
                        else sum++;
                    }
                    if(flag && sum == count){
                        System.out.println(i + " " + j);
                        return true;
                    }
                }
            }
        }
        return false;
    }
}