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

문제 링크

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

문제 설명

고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

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

제한사항

알고리즘: 구현, 브루트 포스

풀이

이 문제는 주어진 열쇠로 자물쇠를 열 수 있는지 없는지 출력하는 문제다.

열쇠는 두 가지 연산이 존재한다.

1. 이동
2. 회전

M, N은 20 이하이기 때문에 구현이 복잡한 완전 탐색 문제다.

내구 구현한 방식은 이렇다.
회전은 총 3번만 하면 된다. (90도 회전, 180도 회줜, 270도 회전)
그리고 열쇠 돌기를 이동시키는데 x, y 방향으로 최대 |M|까지만 가면 된다. 그 이상은 돌기가 다 사라진다.

그래서 한 번 움직이고, 자물쇠를 열 수 있는지 확인하고 또 움직이고를 반복 했다.
(자물쇠를 열 수 있는지 확인하는 메소드인 check_open()은 퍼즐 조각 채우기와 같은 방법으로 구현했다.)

움직이는 연산은 최대 (2M + 1) * (2M + 1)이기 때문에 이러한 완전 탐색 풀이가 가능하다.

소스 코드

import java.util.*;
class Move {
    int x, y;
    Move(int x, int y) {
        this.x = x; //좌우로 얼마나 이동했는지
        this.y = y; //상하로 얼마나 이동했는지
    }
}

class Point {
    int x, y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
class Solution {
    static final int[] dx = {-1, 0, 1, 0};
    static final int[] dy = {0, -1, 0, 1};
    static boolean[][] visited;
    static int[][] key;
    static int M;
    static boolean answer = false;
    static ArrayList<ArrayList<Point>> lock_peace_list = new ArrayList<>();
    public boolean solution(int[][] Key, int[][] lock) {
        M = Key.length;
        key = Key;
        ArrayList<Point> lock_peace = find_peace(lock, 0);
        if(lock_peace.size() == 0) return true;
        for(int i=0; i<4; i++) {
            lock_peace_list.add(standardization_peace(lock_peace));
            lock_peace = rotation_peace(lock_peace);
        }
        visited = new boolean[2 * M + 1][2 * M + 1]; //(M, M)이 new Move(0, 0)
        BFS();
        return answer;
    }
    
    static void BFS() {
        Queue<Move> que = new LinkedList<>();
        que.add(new Move(0, 0));
        visited[M][M] = true;
        while(que.size() != 0) {
            Move n = que.poll();
            if(check_open(n)) {
                answer = true;
                return;
            }
            for(int i=0; i<4; i++) {
                int nx = n.x + dx[i];
                int ny = n.y + dy[i];
                if((0 <= (nx + M) && (nx + M) <= 2*M) && (0 <= (ny + M) && (ny + M) <= 2*M)) {
                    if(!visited[nx + M][ny + M]) {
                        visited[nx + M][ny + M] = true;
                        que.add(new Move(nx, ny));
                    }
                }
            }
        }
    } 
    
    static boolean check_open(Move m) {
        int[][] m_key = move_key(m);
        ArrayList<Point> key_peace = standardization_peace(find_peace(m_key, 1));
        if(key_peace.size() == lock_peace_list.get(0).size()) {
            for(int i=0; i<lock_peace_list.size(); i++) {
                if(same_peace(key_peace, lock_peace_list.get(i))) return true;
            }
        }
        return false;
    }
    
    static int[][] move_key(Move m) {
        int[][] m_key = new int[M][M];
        for(int i=0; i<key.length; i++) {
            int ny = i + m.y;
            for(int j=0; j<key[i].length; j++) {
                int nx = j + m.x;
                if(key[i][j] == 1 && ((0 <= nx && nx <= M-1) && (0 <= ny && ny <= M-1))) m_key[ny][nx] = 1;
            }
        }
        return m_key;
    }
    
    static boolean same_peace(ArrayList<Point> key_peace, ArrayList<Point> lock_peace) {
        for(int i=0; i<lock_peace.size(); i++) {
            if((key_peace.get(i).x != lock_peace.get(i).x) || (key_peace.get(i).y != lock_peace.get(i).y)) return false;
        }
        return true;
    }
    
    static ArrayList<Point> find_peace(int[][] arr, int v) {
        ArrayList<Point> peace = new ArrayList<>();
        for(int i=0; i<arr.length; i++) {
            for(int j=0; j<arr[i].length; j++) {
                if(arr[i][j] == v) peace.add(new Point(j, i));
            }
        }
        return peace;
    }
    
    static ArrayList<Point> standardization_peace(ArrayList<Point> peace) {
        sort_peace(peace);
        ArrayList<Point> s_peace = new ArrayList<>();
        for(int i=0; i<peace.size(); i++) s_peace.add(new Point(peace.get(i).x - peace.get(0).x, peace.get(i).y - peace.get(0).y));
        return s_peace;
    }
    
    static void sort_peace(ArrayList<Point> peace) {
        Collections.sort(peace, (a, b) -> {
            if(a.y - b.y < 0) return -1;
            else if(a.y - b.y > 0) return 1;
            else {
                if(a.x - b.x < 0) return -1;
                else if(a.x - b.x > 0) return 1;
            }
            return 0;
        });
    }
    
    static ArrayList<Point> rotation_peace(ArrayList<Point> peace) {
        //90도 시계 방향 회전
        ArrayList<Point> r_peace = new ArrayList<>();
        for(int i=0; i<peace.size(); i++) r_peace.add(new Point((M-1) - peace.get(i).y, peace.get(i).x));
        return r_peace;
    }
}