[코테연습] 자물쇠와 열쇠

https://school.programmers.co.kr/learn/courses/30/lessons/60059?language=java

프로그래머스

 

 

• 문제타입:
  • 조합, 회전 및 슬라이딩 문제로, 두 개의 2D 배열(열쇠와 자물쇠)을 이용해 맞추는 문제입니다. 열쇠는 회전 및 슬라이딩이 가능하며, 자물쇠의 홈에 열쇠의 돌기 부분을 맞추는 방식으로 자물쇠를 열 수 있는지 확인하는 문제입니다.
• 문제 분석:
  • 열쇠의 회전: 열쇠는 90도씩 회전하여 총 4가지 방향으로 시도할 수 있습니다. 각 회전에서 자물쇠에 맞춰야 합니다.
  • 슬라이딩: 열쇠는 자물쇠의 여러 위치에 맞춰 슬라이딩 할 수 있습니다. 자물쇠보다 열쇠가 작기 때문에 자물쇠의 크기만큼만 이동이 가능합니다.
  • 자물쇠가 열리기 위한 조건: 자물쇠의 **홈 부분(0)**은 열쇠의 **돌기 부분(1)**에 맞게 채워져야 하며, 열쇠의 돌기 부분과 자물쇠의 돌기 부분은 겹치지 않음. 자물쇠가 열리려면, 자물쇠의 홈이 모두 채워져야 합니다.
• 문제 풀이:
  1. 열쇠 회전: 열쇠를 90도씩 회전하여 4가지 경우를 체크합니다.
  2. 슬라이딩: 각 회전 후, 열쇠를 자물쇠 위에 다양한 위치에 맞춰 봅니다.
  3. 자물쇠 열리기 여부 확인: 열쇠가 자물쇠에 맞으면 자물쇠의 홈이 모두 채워져 있는지 확인합니다.

 

import java.util.*;

class Solution {
    public boolean solution(int[][] key, int[][] lock) {
        int N = lock.length;
        int M = key.length;

        // 4번 회전하면서 열쇠를 시도
        for (int rotation = 0; rotation < 4; rotation++) {
            key = rotate(key); // 열쇠를 90도 회전

            // 자물쇠에 맞춰서 열쇠를 이동시키기
            for (int i = -M + 1; i < N; i++) {
                for (int j = -M + 1; j < N; j++) {
                    if (check(lock, key, i, j)) {
                        return true; // 자물쇠가 열리면 true 반환
                    }
                }
            }
        }

        return false; // 자물쇠가 열리지 않으면 false 반환
    }

    // 자물쇠가 열렸는지 확인하는 함수
    boolean check(int[][] lock, int[][] key, int startX, int startY) {
        int N = lock.length;
        int M = key.length;

        // 자물쇠의 복사본
        int[][] tempLock = new int[N][N];
        for (int i = 0; i < N; i++) {
            tempLock[i] = Arrays.copyOf(lock[i], N);
        }

        // 열쇠를 자물쇠에 맞춰 놓기
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < M; j++) {
                int x = startX + i;
                int y = startY + j;
                if (x >= 0 && x < N && y >= 0 && y < N && key[i][j] == 1) {
                    // 겹치는 부분이 있으면 실패
                    if (tempLock[x][y] == 1) {
                        return false;
                    }
                    tempLock[x][y] = 1;
                }
            }
        }

        // 자물쇠가 완전히 열렸는지 확인 (자물쇠가 모두 1로 채워졌는지 확인)
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 자물쇠의 홈(0) 부분이 모두 채워졌다면 열림
                if (lock[i][j] == 0 && tempLock[i][j] != 1) {
                    return false;
                }
            }
        }

        return true;
    }

    // 90도 회전하는 함수
    int[][] rotate(int[][] key) {
        int n = key.length;
        int m = key[0].length;
        int[][] newKey = new int[m][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                newKey[j][n - 1 - i] = key[i][j];
            }
        }
        return newKey;
    }
}

 

 

 

자물쇠에 맞춰서 열쇠를 이동시키기 부분 설명

자물쇠에 맞춰서 열쇠를 이동시키는 부분은 핵심적인 로직입니다. 열쇠를 자물쇠의 홈 부분에 정확하게 맞추려면 열쇠의 위치를 자물쇠의 여러 부분에 맞춰서 이동시켜야 합니다. 이를 위해서는 다음과 같은 절차를 따릅니다.

1. 슬라이딩 범위 설정:
   • 열쇠는 자물쇠보다 크기가 작기 때문에 자물쇠 위에서 슬라이딩할 수 있는 범위가 제한적입니다.
   • 자물쇠의 크기가 N x N이고, 열쇠의 크기가 M x M일 때, 열쇠는 자물쇠의 범위 내에서 이동할 수 있습니다.
   • 슬라이딩 범위는 -M + 1부터 N까지입니다. 이 범위는 열쇠가 자물쇠의 크기에 맞춰 자물쇠 위에서 이동할 수 있는 모든 위치를 커버합니다.
2. 슬라이딩 위치 계산:
   • 열쇠가 자물쇠의 (i, j) 위치에 맞춰져야 한다면, 열쇠의 시작 위치 (i, j)는 자물쇠의 왼쪽 상단 위치 (0, 0)에서 -M + 1에서 N까지의 범위로 이동할 수 있습니다.
   • startX와 startY는 열쇠가 자물쇠 위에 놓일 시작 좌표입니다. 이 위치를 기준으로 열쇠를 자물쇠 위에 올려놓고, 해당 위치에 열쇠를 맞춰서 자물쇠가 열리는지 확인합니다.
3. 열쇠와 자물쇠 맞추기:
   • 열쇠를 자물쇠 위에 놓고, 각 위치에 대해 열쇠의 **돌기 부분(1)**이 자물쇠의 **홈 부분(0)**에 맞는지, 또 돌기 부분끼리 겹치지 않는지 확인합니다.
   • 자물쇠의 **홈(0)**이 열쇠의 **돌기(1)**에 정확히 들어맞아야 자물쇠가 열립니다.
   • check() 함수 내에서 이 부분을 처리하며, 열쇠의 위치를 조정하면서 겹치는 부분이 있는지 확인합니다.
4. 중앙 부분 확인:
   • 자물쇠의 홈이 모두 채워졌는지 확인하려면, 자물쇠의 중앙 부분이 모두 1로 채워져야 합니다.
   • 자물쇠의 홈(0) 부분을 열쇠의 돌기(1)로 완전히 채우고, 자물쇠의 돌기 부분(1)과 열쇠의 돌기 부분(1)이 겹치지 않도록 해야 합니다.

 

구체적인 코드 흐름

for (int i = -M + 1; i < N; i++) {
    for (int j = -M + 1; j < N; j++) {
        // 열쇠를 자물쇠 위에 위치시키고 자물쇠가 열리는지 확인
        if (check(lock, key, i, j)) {
            return true; // 자물쇠가 열리면 true 반환
        }
    }
}

 

• for (int i = -M + 1; i < N; i++)와 for (int j = -M + 1; j < N; j++)는 열쇠가 자물쇠의 범위 내에서 이동할 수 있는 모든 위치를 커버합니다.
• check(lock, key, i, j)는 열쇠를 자물쇠의 (i, j) 위치에 맞춰 놓고, 자물쇠의 홈을 모두 채울 수 있는지 확인합니다.