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

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

위와 같이 Key, Lock이 주어졌을 때, Key의 돌기 부분에 Lock의 홈 부분에 딱 맞으면 true 아니면 false이다. 이 때 Key는 90도 시계방향으로 회전이 가능하고 동시에 상하좌우로 미루기가 가능하다.

위 사진같은 경우엔 Key를 시계방향 90도로 뒤집고, 우측으로 한 칸 밑으로 한 칸 내리면 된다.
Key와 Lock의 크기는 최소 3에서 최대 20까지이다.

이 문제를 해결하기 위해서 Key를 직접 회전하거나 움직이지 않고, 반대로 Lock에서 홈인 부분을 추출해서 이를 회전해가면서 Key에 해당 패턴이 있는지를 체크했다.

단순 구현이라 설명할게 많이 없다...

코드는 아래와 같다.

#include <string>
#include <vector>

using namespace std;

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = true;
    
    int n = lock.size();
    int row_start, row_end;
    int col_start, col_end;
    bool fin = false;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            if(lock[i][j] == 0) {
                row_start = i;
                fin = true;
                break;
            }
        }
        if(fin) break;
    }
    fin = false;
    for(int i=n-1;i>=0;i--) {
        for(int j=0;j<n;j++) {
            if(lock[i][j] == 0) {
                row_end = i;
                fin = true;
                break;
            }
        }
        if(fin) break;
    }
    fin = false;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            if(lock[j][i] == 0) {
                col_start = i;
                fin = true;
                break;
            }
        }
        if(fin) break;
    }
    fin = false;
    for(int i=n-1;i>=0;i--) {
        for(int j=0;j<n;j++) {
            if(lock[j][i] == 0) {
                col_end = i;
                fin = true;
                break;
            }
        }
        if(fin) break;
    }
    
    int row_size = row_end - row_start + 1;
    int col_size = col_end - col_start + 1;
    int size = row_size > col_size ? row_size : col_size;
    int clock_pattern[4][size][size];
    for(int s=0;s<4;s++) 
        for(int i=0;i<size;i++) 
            for(int j=0;j<size;j++) 
                clock_pattern[s][i][j] = 0;
            
    for(int i=0;i<row_size;i++) 
        for(int j=0;j<col_size;j++) 
            clock_pattern[0][i][j] = lock[i + row_start][j + col_start] ? 0 : 1;

    for(int s=1;s<4;s++) 
        for(int i=0;i<size;i++) 
            for(int j=0;j<size;j++) 
                clock_pattern[s][i][j] = clock_pattern[s - 1][size - j - 1][i];
    
    if(row_size > col_size) {
        int diff = row_size - col_size;
        for(int i=0;i<size;i++) 
            for(int j=0;j<size-diff;j++) 
                clock_pattern[2][i][j] = clock_pattern[2][i][j + diff];
        
        for(int i=0;i<size-diff;i++) 
            for(int j=0;j<size;j++) 
                clock_pattern[3][i][j] = clock_pattern[3][i + diff][j];
    } else if(row_size < col_size) {
        int diff = col_size - row_size;
        for(int i=0;i<size;i++) 
            for(int j=0;j<size-diff;j++) 
                clock_pattern[1][i][j] = clock_pattern[1][i][j + diff];
        
        for(int i=0;i<size-diff;i++) 
            for(int j=0;j<size;j++) 
                clock_pattern[2][i][j] = clock_pattern[2][i + diff][j];
    }
    
    int lock_count = 0;
    for(int i=0;i<row_size;i++) 
        for(int j=0;j<col_size;j++) 
            lock_count += clock_pattern[0][i][j];

    int key_size = key.size();
    for(int i=0;i<=key_size-row_size;i++) {
        for(int j=0;j<=key_size-col_size;j++) {
            int cnt = 0;
            bool fail = false;
            for(int ii=i;ii<i+row_size;ii++) {
                for(int jj=j;jj<j+col_size;jj++) {
                    if(key[ii][jj] == 1 && clock_pattern[0][ii - i][jj - j] == 1)
                        cnt++;
                    if(key[ii][jj] == 1 && clock_pattern[0][ii - i][jj - j] == 0)
                        fail = true;
                }
            }
            if(cnt == lock_count && !fail)
                return true;
        }
    }
    for(int i=0;i<=key_size-col_size;i++) {
        for(int j=0;j<=key_size-row_size;j++) {
            int cnt = 0;
            bool fail = false;
            for(int ii=i;ii<i+col_size;ii++) {
                for(int jj=j;jj<j+row_size;jj++) {
                    if(key[ii][jj] == 1 && clock_pattern[1][ii - i][jj - j] == 1)
                        cnt++;
                    if(key[ii][jj] == 1 && clock_pattern[1][ii - i][jj - j] == 0)
                        fail = true;
                }
            }
            if(cnt == lock_count && !fail)
                return true;
        }
    }
    for(int i=0;i<=key_size-row_size;i++) {
        for(int j=0;j<=key_size-col_size;j++) {
            int cnt = 0;
            bool fail = false;
            for(int ii=i;ii<i+row_size;ii++) {
                for(int jj=j;jj<j+col_size;jj++) {
                    if(key[ii][jj] == 1 && clock_pattern[2][ii - i][jj - j] == 1)
                        cnt++;
                    if(key[ii][jj] == 1 && clock_pattern[2][ii - i][jj - j] == 0)
                        fail = true;
                }
            }
            if(cnt == lock_count && !fail)
                return true;
        }
    }
    for(int i=0;i<=key_size-col_size;i++) {
        for(int j=0;j<=key_size-row_size;j++) {
            int cnt = 0;
            bool fail = false;
            for(int ii=i;ii<i+col_size;ii++) {
                for(int jj=j;jj<j+row_size;jj++) {
                    if(key[ii][jj] == 1 && clock_pattern[3][ii - i][jj - j] == 1)
                        cnt++;
                    if(key[ii][jj] == 1 && clock_pattern[3][ii - i][jj - j] == 0)
                        fail = true;
                }
            }
            if(cnt == lock_count && !fail)
                return true;
        }
    }
    return false;
}