[코딩테스트 준비] 카카오 2020 Recruitment 문제 :: 자물쇠와 열쇠

자물쇠와 열쇠

문제

https://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 함수를 완성해주세요.

제한사항

• 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은 돌기 부분을 나타냅니다.

---

코드

#include <string>
#include <vector>

using namespace std;

void turn90(vector<vector<int>> & arr){
    // 90도 회전
    vector<vector<int>> tmp(arr.size(), vector<int>(arr.size(),-1));
    for(int i=0; i<arr.size(); i++){
        for(int j=0; j<arr.size(); j++){
            tmp[j][arr.size()-1-i] = arr[i][j];
        }
    }
    arr = tmp;
}

bool isItFit(vector<vector<int>>& key,vector<vector<int>>& lock, int x, int y){
    // 해당 key가 lock에 맞는지 확인하는 함수
    vector<vector<int>> tmp(lock);
    // 확인을 위한 임의의 vector
    for(int i=0; i<key.size(); i++){
        for(int j=0; j<key.size(); j++){
            if(y+j<0 || x+i<0 || y+j>=lock.size() || x+i>=lock.size())
                // lock을 벗어난 key 범위
                continue;
            tmp[y+j][x+i]=key[j][i]+lock[y+j][x+i];
            // 겹치는 부분은 계산해서 반영
        }
    }
    for(int i=0; i<lock.size(); i++){
        for(int j=0; j<lock.size(); j++){
            // 결국 tmp에는 기존의 lock에서 겹치는 부분만 새로 계산되어나옴 => key가 맞다면 모든 수가 1이어야함
            if(tmp[j][i]!=1)
                return false;
        }
    }
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    int size = lock.size();
    int ksize = key.size();
    for(int i=0; i<4; i++){ // 방향
        for(int j=-ksize; j<size+ksize; j++){ // 가로
            for(int k=-ksize; k<size+ksize; k++){ // 세로
                if(isItFit(key, lock, j, k))
                    return true;
            }
        }
        turn90(key); // 회전
    }
    return false;
}

 

풀이

풀이는 다음과 같은 사고과정으로 생각하였다.

1. 완전탐색이 가능한 지 보자.
2. 입력 M과 N은 20이하이다.
3. key는 한 줄만 겹칠 수도 있으므로, 좌우 / 위아래 가 각각 58가지 경우가 나올 수 있다.

예를 들어 아래의 key와 lock이 있을 때, key를 맞추는 방법은 다음과 같다.

반시계방향으로 90도 회전(or 시계방향으로 270도 회전) 후 오른쪽으로 2칸 왼쪽으로 2칸 이동하는 방법이다.

따라서, 위의 예처럼 key는 lock과 겹쳤을 때를 기준(0)으로 상하, 좌우 방향으로 -2 ~ 2 까지 이동할 수 있다.

즉, 최대의 M, N인 20을 생각하면 상하좌우로 19칸씩 더 갈 수 있으니까 20+19x2의 경우의 수인 58의 경우의 수가 상하, 좌우에 각각 생기고 이를 곱하면 전체 경우의 수인 58^2 = 3364가 나온다.

4. 4가지 방향에 대해서 고려한다.

여기서 4가지 방향에 대해 key가 맞는지 모두 판단해야하므로, 4를 곱해주면 13,456이다.

5. 각 경우에 key가 적합한 지 확인하는 확인해야한다.

key가 적합한 지 확인하려면 lock이 모두 채워져있는지 확인하면 되므로, lock의 최대 가로/세로 길이인 20을 제곱해주면 된다. for문을 2번 중첩해서 확인한다고 가정했을 때의 시간복잡도이다.

400을 13,456과 곱해주면 5,382,400가 되고 이는 10^7보다 작으므로 시간복잡도 상 문제가 없어보인다.

---

만약 완전탐색이 불가능했다면, 다른 방법을 찾아야했겠지만 다행히도 가능하다.

위의 사고흐름대로 코드 변환하는 과정을 기술해보자.

• for문 돌면서 시계방향 4회전
  • 중첩 for문 돌면서 좌=>우
    • 중첩 for문 중첩으로 돌면서 위 => 아래
      • 키가 맞는지 확인 (더해서 1이 안되면 break)

결국 회전하고 이동시키면서 key와 lock을 더했을 때, lock이 모두 1이면 true를 반환하면 된다.

 

다른 사람의 풀이

다 비슷하게 푼 듯하다. 다만 나의 경우 푸는 시간이 너무 느렸다. 이유는 코드를 대충 작성하고 오류 개선에 시간을 많이 할애했기 때문이다. 주의하자!