[구현] (프로그래머스 Lv 3) 자물쇠와 열쇠

문제

• 문제 링크
• 문제 설명: MxM 2차원 배열인 열쇠를 회전/이동 하여 NxN 2차원 배열인 자물쇠의 모든 홈 부분과 열쇠의 돌기가 딱 맞게 매칭 시킬 수 있으면 true, 아니면 false를 반환하는 함수 작성.
  • 자물쇠의 돌기와 열쇠의 돌기가 마주치면 안됌.
  • 열쇠의 범위가 자물쇠 범위 밖에 있을 경우 영향을 주지 않음.
• 입력
  • 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은 돌기 부분을 나타냅니다.
• 출력: 매칭이 되면 true, 아니면 false

key	lock	result
[[0, 0, 0], [1, 0, 0], [0, 1, 1]]	[[1, 1, 1], [1, 1, 0], [1, 0, 1]]	true

풀이

• 2차원 배열의 크기가 크지 않기 때문에 naive하게 열쇠를 돌리는 함수(rotate)와 1칸씩 움직이면서 열쇠와 자물쇠가 겹치는 부분에 대해 모든 원소가 매칭이 되는지 검사하는 함수(canLock)를 호출
  • 말은 쉬운데 구현하는데 시간이 오래 걸렸던 문제
• rotate 함수를 작성할 때 열쇠의 배열 크기 M이 홀수이면 맨 중앙에 있는 값은 그대로 복사해주어야 함
• canLock 함수를 최대한 간단하게 구현하기 위해 각 열쇠와 자물쇠가 겹치는 위치의 좌표만 받음.
  • canLock(pii& ks, pii& ls, int yGap, int xGap) := 열쇠의 좌측상단 좌표 ks, 자물쇠의 좌측상단 좌표 ls, 그리고 y축 오프셋과 x축 오프셋.
• 움직일 때는 열쇠의 맨 끝 원소[(N-1,N-1) 좌표]와 자물쇠의 첫번째 원소[(0,0) 좌표]를 맞물리는 것을 시작으로 x축으로 끝까지 이동하고 다 이동하면 y축으로 한 칸씩 늘리면서 진행 M 은 항상 N 이하이기 때문에 M이 N에 포함될 때 열쇠의 겹치는 구간은 변함이 없지만 자물쇠의 구간은 계속 바꾸어 주어야 하는데 주의
• 이런 문제는 단정문(assertion)이 불가피하다.
• 움직이면서 canLock 이 1번이라도 true이면 true를 반환하도록 구현함

#include <string>
#include <vector>
#include <cassert>
#define Y first
#define X second
using namespace std;
typedef pair<int,int> pii;

// 자물쇠를 시계 방향으로 90도 회전하는 함수
void rotate(vector<vector<int>>& old_key) {
    int n = old_key.size(), i = 0;
    vector<vector<int>> new_key(n, vector<int> (n, 0));
    for (; i < n >> 1; i++) { // 가장자리에서부터 회전할 때 최대 깊이는 길이의 절반
        for (int j = i; j < n-i; j++) {
            // top (i,i)~(i,n-i-1) -> right-side (i,n-i-1)~(n-i-1,n-i-1)
            new_key[j][n-i-1] = old_key[i][j];
            // right-side (i,n-i-1)~(n-i-1,n-i-1) -> bottom (n-i-1,n-i-1)~(n-i-1,i)
            new_key[n-i-1][n-j-1] = old_key[j][n-i-1];
            // bottom (n-i-1,i)~(n-i-1,n-i-1) -> left-side (i,i)~(n-i-1,i)
            new_key[j][i] = old_key[n-i-1][j];
            // left-side (i,i)~(n-i-1,i) -> top (i,n-i-1)~(i,i)
            new_key[i][n-j-1] = old_key[j][i];
        }
    }
    if (n & 1) new_key[i][i] = old_key[i][i]; // 길이가 홀수이면 맨 중앙값은 그대로 복사
    old_key = new_key;
}

int numZerosOfLock;

// 겹치는 구간에 모든 자물쇠의 홈이 문제없이 매칭된다면 true 반환
bool canLock(vector<vector<int>>& key,
             vector<vector<int>>& lock,
             pii& ks, pii& ls, int yGap, int xGap)
{
    int numMatches = 0;
    for (int dy = 0; dy <= yGap; dy++) {
        for (int dx = 0; dx <= xGap; dx++) {
            auto& kVal = key[ks.Y + dy][ks.X + dx];
            auto& lVal = lock[ls.Y + dy][ls.X + dx];
            if (kVal == lVal) return false;
            if (kVal && !lVal) numMatches++;
        }
    }
    return numMatches == numZerosOfLock;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    int n = lock.size();
    int m = key.size();
    numZerosOfLock = 0;
    for (int y = 0; y < n; y++)
        for (int x = 0; x < n; x++)
            if (lock[y][x] == 0)
                numZerosOfLock++; // 맨 처음에 자물쇠의 홈의 개수 계산
    // 매 회전마다 시도
    for (int i = 0; i < 4; i++) {
        rotate(key);
        pii ks, ke, ls, le;
        ks.Y = ke.Y = m-1;
        ls.Y = le.Y = 0;
        while (ke.Y >= 0) {
            ls.X = le.X = 0;
            ks.X = ke.X = m-1;
            while (ke.X >= 0) { // X축으로 1칸씩 이동하면서 겹치는 구간을 검사
                if (canLock(key, lock, ks, ls, ke.Y-ks.Y, ke.X-ks.X))
                    return true;
                if (ks.X > 0) ks.X--; // 열쇠는 자물쇠 배열에서 왼->오 이동할 때 x좌표가 0으로 수렴
                else ls.X++; // 열쇠가 자물쇠의 끝에 도달하면 열쇠의 구간의 시작 좌표 x값을 늘려줌
                if (le.X < n-1) le.X++; // 열쇠가 왼->오 이동할 때 자물쇠 구간의 끝 좌표 x값을 늘려줌
                else ke.X--; // 열쇠가 자물쇠의 끝에 도달하면 열쇠의 구간의 끝 좌표 x값을 줄여줌
                assert (le.X - ls.X == ke.X - ks.X);
            }
            if (ks.Y > 0) ks.Y--; // 열쇠가 자물쇠 배열에서 위->아래 이동할 때 y좌표는 0으로 수렴
            else ls.Y++; // 열쇠가 자물쇠의 끝에 도달하면 열쇠의 구간의 시작 좌표 y값을 늘려줌
            if (le.Y < n-1) le.Y++; // 열쇠가 이동하면 자물쇠 배열의 구간의 끝 좌표 y값을 늘려줌
            else ke.Y--; // 열쇠가 자물쇠의 끝에 도달하면 열쇠의 구간의 끝 좌표 y값을 줄여줌
            assert (le.Y - ls.Y == ke.Y - ks.Y);
        }
    }
    return false;
}