[프로그래머스 level3] 자물쇠와 열쇠 (C++)

2020 kakao blind recruitment에서 나왔던 문제로 복잡한 구현문제입니다. (프로그래머스 level3)

문제는 다음과 같습니다.
자물쇠와 열쇠

조건

1. key의 크기 M은 lock의 크기 N 이하이다.
2. key는 이동과 회전이 가능하다. (90,180,270도 모두 가능)
3. key의 돌기부분(1)과 자물쇠의 홈 부분(0)이 일치해야 한다.
4. 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있다.

조건이 참 많은 구현문제입니다.
key의 이동과 회전에 대해서 어떻게 짜야할지 감이 안 잡혀 다음의 티스토리를 참고했습니다.
참고

구현과정

1. 배열을 N+2(M-1)로 만듭니다.
   key가 이동이 가능하기 때문에 lock에 일부만 걸쳐있을 수 있습니다. 따라서 열쇠가 이동가능한 영역은 N+2(M-1) X N+2*(M-1) 가 됩니다.
   => solution() 참고
2. 1에서 구한 배열에 lock 부분 할당하기
   확장된 배열의 중앙에 lock을 할당합니다.
   lock이 아닌부분 -> 2
   lock인 부분 -> 0/1
   lock의 시작좌표 : (0,0) -> (M-1, M-1)
   lock의 종료좌표 : (N,N) -> (배열크기-M, 배열크기-M)
   => make_MAP() 참고
3. key, lock을 비교
   - key (0), lock (0) -> 틀림
   - key (1), lock (1) -> 틀림
   - key (1), lock (0) -> 맞음
   => isUnlock() 참고
4. key의 이동
   key는 N+M-1 만큼 오른쪽, 아래로 움직일 수 있음
   => move_key() 참고
5. key의 회전
   시계방향으로 90도 회전하면
   (y,x) <- (M-1-x,y)
   => rotate_key() 참고

코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<vector<int>> MAP;
int N, M, Size, sum;

void make_MAP(vector<vector<int>> lock)
{
    int y = 0, x = 0;
    for(int i=M-1; i<Size-M+1; i++, y++)
    {
        for(int j=M-1; j<Size-M+1; j++, x++)
        {
            if(lock[y][x]==0) {MAP[i][j] = 0; sum++;}
            else MAP[i][j] = 1;
        }
        x=0;
    }
}
int isUnlock(int y, int x, vector<vector<int>> key)
{
    int idx_x = 0, idx_y = 0;
    int cnt = 0;
    for(int i=y; i<y+M; i++, idx_y++)
    {
        for(int j=x; j<x+M; j++, idx_x++)
        {
            if(key[idx_y][idx_x]==0 && MAP[i][j]==0) return -1;
            if(key[idx_y][idx_x]==1 && MAP[i][j]==1) return -1;
            if(key[idx_y][idx_x]==1 && MAP[i][j]==0) cnt++;
        }
        idx_x=0;
    }
    
    return cnt;
}
void rotate_key(vector<vector<int>> &key)
{
    vector<vector<int>> tmp = key;
    for(int i=0; i<M; i++)
    {
        for(int j=0; j<M; j++)
        {
            tmp[i][j] = key[M-1-j][i];
        }
    }
    key = tmp;
}
bool move_key(vector<vector<int>> key)
{
    for(int i=0; i<4; i++)
    {
        //시작칸수
        for(int j=0; j<M+N-1; j++)
        {
            for(int k=0; k<M+N-1; k++)
            {
                if(isUnlock(j,k,key)==sum)
                {
                    return true;
                }
            }
        }
        rotate_key(key);
    }
    return false;
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = true;
    M = key.size();
    N = lock.size();
    Size = N+(M-1)*2;
    MAP.resize(Size, vector<int>(Size,2));
    
    make_MAP(lock);
    if(!move_key(key)) answer = false;
    return answer;
}

c++ 문법

• 2차원 배열 -> vector <vector<int>> v
  (크기를 모를때 int arr[][] 보다 좋은 듯)
• vector 크기 지정 및 값 할당

1. 선언시 할당
   vector<int> vec(5,1)
2. 재할당 or 선언 이후 할당
   vec.resize(10,2)

[resize 주의할점]
resize하며 더 커지는 경우에만 값이 들어간다.
더 작아지는 경우에는 크기만 작아지고 값이 할당되지는 않는다.

이 코드에서는

MAP.resize(Size, vector<int>(Size,2));

이렇게 사용하였다.
2차원 vector를 size만큼 지정하고 vector (size,2)의 값을 할당한다는 의미
즉 모든 값을 2로 할당