[시뮬레이션] 자물쇠와 열쇠 - 2020 KAKAO BLIND RECRUITMENT

해결 방법

아래 이미지와 같이 x, y 좌표의 범위가 모두 [m-1, m+n-1)인 Lock 구간을 정하고, 모든 경우에 대하여 Key를 맞춰보면 된다. key를 회전하는 경우도 반드시 반영하도록 하자.

 

먼저, board에 lock 구간을 미리 반영해둔다. 입출력 예의 경우에는 다음과 같은 결과가 나올 것이다.

0000000
0000000
0011100
0011000
0010100
0000000
0000000

 

그리고 key를 board에 배치할 수 있는 모든 경우를 따져보면 된다.

각 경우마다 board에 key를 더하고, board의 lock 구간만 탐색해서 1이 아닌 칸이 존재하면 자물쇠를 풀 수 없다고 판단하면 된다.

• lock + key = 0인 경우 : 자물쇠의 홈을 채울 수 없다.
• lock + key = 1인 경우 : 자물쇠의 홈이 채워져 있으며, 자물쇠의 돌기와 열쇠의 돌기가 만나지 않는다.
• lock + key = 2인 경우 : 자물쇠의 돌기와 열쇠의 돌기가 만난다.

그리고 각 경우를 따진 직후에는 반드시 board를 원상 복구 시켜주면 된다.

 

예를 들어, 입출력 예에서 자물쇠를 풀 수 있는 경우를 따져보자.

자물쇠를 풀 수 있는 경우에 해당하는 key는 다음과 같다.

<key>

0000000
0000000
0000000
0000100
0001000
0001000
0000000

그리고 board에 이 key를 더하면 다음과 같은 결과가 나온다.

0000000
0000000
0011100
0011100
0011100
0001000
0000000

위의 결과에서, lock 구간은 모두 1이므로 자물쇠를 풀 수 있다고 판단하는 것이다.

 

 

소스 코드

#include <vector>
#include <algorithm>
using namespace std;
int board[59][59];

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    int m=key.size();
    int n=lock.size();
    bool can_unlock;
    
    vector<vector<int>> key_copy(m, vector<int>(m));
    copy(key.begin(), key.end(), key_copy.begin());
    
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) board[m-1+i][m-1+j]=lock[i][j]; // 자물쇠 배치
    
    for(int r=0;r<4;r++){
        for(int i=0;i<m;i++) for(int j=0;j<m;j++) key[i][j]=key_copy[m-1-j][i]; // 시계 방향 90도 회전
        copy(key.begin(), key.end(), key_copy.begin()); // 회전한 키 복사
        
        for(int i=0;i<m+n-1;i++){ // i, j = 검사 시점
            for(int j=0;j<m+n-1;j++){
                for(int x=0;x<m;x++) for(int y=0;y<m;y++) board[i+x][j+y]+=key[x][y]; // board + key
                can_unlock=true;
                for(int x=0;x<n;x++){
                    for(int y=0;y<n;y++){
                        if(board[m-1+x][m-1+y]!=1) { // board 값이 1이 아닌 경우에는 자물쇠를 풀 수 없다.
                            can_unlock=false;
                            break;
                        }
                    }
                    if(!can_unlock) break;
                }
                if(can_unlock) return true; // 자물쇠를 풀 수 있는 경우
                for(int x=0;x<m;x++) for(int y=0;y<m;y++) board[i+x][j+y]-=key[x][y]; // board - key (원상 복구)
            }
        }
    }
    return answer;
}

 

테스트케이스 38개 모두 정답

 

 

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/60059