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

프로그래머스의 자물쇠와 열쇠 (Lv3) 문제이다.

 

[ 문제풀이 ]

문제나 꽤나 복잡해 보인다..

문제에 접근하는 전체적인 접근방법부터 구체적인 과정까지 단계별로 해결해가보자.

 

#1. 접근방법

열쇠와 자물쇠가 주어졌을 때, 자물쇠의 모든 홈 부분과 열쇠의 돌기 부분이 정확하게 일치해야 자물쇠를 열 수 있다.

그리고 이 때, 열쇠로 자물쇠를 열 수 있는지를 판단해야 하는 문제이다.

그런데 문제는 ! 열쇠와 자물쇠의 크기가 항상 같은 것도 아니다. 다를 수도 있고, 열쇠는 회전시킬수도 있다.

그리고 열쇠의 일부만 자물쇠에 맞출수도 있다.

예를 들면 다음과 같다.

왼쪽 그림을 열쇠, 오른쪽 그림을 자물쇠라고 생각해보자.

그리고 갈색으로 칠해진 부분을 돌기, 흰색으로 표시되어 있는 부분을 홈이라고 생각해보자.

위의 그림은 얼추 맞출 수 없을 것만 같다는 생각이 든다.

왜냐하면, 자물쇠의 홈 부분을 열쇠의 돌기 부분을 열쇠를 회전시킨다면 채울 수는 있겠지만, 채우는 순간 다른 부분이 자물쇠의 돌기 부분과 열쇠의 홈 부분이 만나버리기 때문이다.

하지만 ! 위는 결국 열 수 있게 된다. 다음과 같이 결합해 버리면 자물쇠를 열 수 있다.

열쇠를 위와 같이 만들어 버리면 되기 때문이다. 즉 ! 자물쇠의 범위를 벗어나게 열쇠를 만들더라도, 결국 어떻게 해서든지 자물쇠의 모든 홈 부분을 열쇠의 돌기 부분들로 채우기만 하면 된다.

그래서, 우리는 이 과정을 위해서 자물쇠의 크기를 매우 크게 만들어 줄 것이다.

그리고, 이 큰 맵에서 열쇠를 움직이고 돌리고 해주면서 비교를 할 것이다.

구체적으로 알아보자.

 

#2. 새로운 자물쇠 맵 만들기

위의 예시를 다시한번 가져와보자.

이런 경우에, 자물쇠의 범위를 벗어나도록 열쇠를 세팅함으로써 자물쇠를 열 수 있다는 이야기를 하였다.

이를 위해서 자물쇠를 정말 크게 한번 만들어보자.

예를 들어서, 자물쇠가 위의 예시에서처럼 3x3크기가 아닌, 다음과 같은 크기를 가진 자물쇠라고 생각을 해보자.

자물쇠가 위와 같은 크기를 가졌다고 생각을 해보자.

3 x 3 크기가 아닌, 7 x 7 크기를 가졌고, 그 중에서 가운데 찐하게 테두리가 표시된 부분에만 자물쇠의 실제 부분이 만들어져 있다고 생각을 해보자.

지금 이게 뭘하는 걸까 ?? 갑자기 맵은 왜 크게 만들었고, 왜 큰 맵 한가운데에 자물쇠의 실제부분을 만들고 이걸 왜하고 있는걸까 ?? 열쇠를 다음과 같이 움직이기 위해서이다.

열쇠를 위와 같이 움직이기 위해서이다.

바로, 빨강색 테두리로 이루어진 사각형들이 열쇠를 표현한 것이다.

가장 왼쪽 위의 좌표에서부터 가장 우측 하단의 좌표까지 열쇠를 움직일 것이다.

왜 저렇게 움직이도록 구현을 한 것일까 ?? 바로, "자물쇠의 범위 밖에 열쇠를 세팅하는 경우"를 위해서이다.

우리가 진행했던 위의 예시에서도 그랬듯이, 열쇠를 자물쇠의 범위 밖에 오도록 세팅을 해야만 정답을 구할 수가 있는 경우도 존재한다. 이 부분을 위해서 위와 같이 구현을 한 것이다.

 

지금부터는 위와 같이 자물쇠와 열쇠의 크기를 토대로, 새로운 큰 자물쇠 맵을 다시 만들 것이다.

자물쇠의 한 변의 길이 = N , 열쇠의 한 변의 길이 = M 이라고 가정해보자.

위의 예시에서는 N = 3, M = 3인 경우였다. 그리고 이 때, 한 변의 길이가 7인 새로운 맵이 만들어 졌다.

그럼 한 가지 예시를 더 생각해보자.

왼쪽 그림이 열쇠이고, 오른쪽 그림이 자물쇠이다. 위의 그림을 새로운 큰 맵으로 만들기 위해서는 다음과 같이 만들어야 할 것이다.

위와 같이 맵을 만들 수 있을 것이다.

즉, N = 3 , M = 2 일 때는 한 변의 길이가 5인 새로운 자물쇠 맵이 만들어 졌다.

그럼, 자물쇠의 한 변의 길이가 N, 열쇠의 한 변의 길이가 M 인 경우를 계산해보자.

우리는 결국, 보라색 화살표로 표시되어 있는 저 칸수가 몇 칸이 추가되는지만 구하면 될 것이다.

저 보라색 화살표로 표시된 칸수가 K 칸이라고 가정한다면, 우리가 만들 새로운 자물쇠 맵의 한 변의 길이는

N + K + K 가 될 것이다. 그럼 K는 어떻게 구할 수 있을까 ??

잘 보면 알겠지만, M - 1이 된다. 열쇠가 가진 한 변의 길이인 'M'에서, 즉, 열쇠가 가진 한 변의 칸 수인 M개의 칸에서 자물쇠와 한 칸을 겹치게 만든 남은 칸수, 즉 ! M - 1칸 만큼을 자물쇠 크기의 양쪽에 더해주면 되는 것이다.

정리해보면, 새로운 자물쇠 맵의 크기는 N + (M - 1) + (M - 1)이 될 것이고, 이를 정리해보면 N + 2 * (M - 1)이 될 것이다.

우리는, 한 변의 길이가 N + 2 * (M - 1)인 새로운 자물쇠 맵을 만들어 줄 것이다.

 

#3. 자물쇠 맵 채우기

그럼, 이제 #2에서 만든 새로운 맵을 한번 채워보자.

채운다는게 뭘 의미하는 것일까 ??

바로 이 그림처럼 만든다는 것이다. 우리가 만든 큰 맵에서, 가장 한 가운데 자물쇠의 부분을 표시한다는 것이다.

위의 맵은 열쇠의 크기가 3 x 3 이고, 자물쇠의 크기가 3 x 3 일 때,

3 + (3 - 1) * 2 로 만든 7 x 7 크기의 맵이다.

가장 왼쪽 위의 좌표를 (0 , 0)이라고 가정했을 때, 우리는 (2 , 2)를 시작점으로 3 x 3 크기의 자물쇠 부분을 만들어 주어야 한다. 가장 우측 하단의 좌표는 (4 , 4)가 될 것이다.

그럼, 열쇠의 크기가 M x M 이고 자물쇠의 크기가 N x N 일때를 계산해보자.

자물쇠가 들어가야 할 가장 왼쪽 상단의 좌표는 (M - 1 , M - 1)이 될 것이다.

그럼, 가장 우측 하단의 좌표는 어떻게 될까 ???

새로운 맵의 한 변의 길이를 Size 라고 가정한다면, 가장 우측 하단의 좌표는 (Size - M , Size - M ) 이 될 것이다.

위의 예시를 통해서 보면, (7 - 3 , 7 - 3) 이 되는 것이다.

이를 통해서, 새로운 맵에서 자물쇠를 채워넣어주자.

이 때 ! 원래 자물쇠의 영역이 아닌 외부 영역들에 대해서는 '2'라는 "원래의 영역이 아님을 뜻하는 값" 을 넣어주었다.

#2와 #3의 부분을 코드로 보면 다음과 같다.

int Size = N + 2 * (M - 1);
vector<vector<int>> MAP(Size, vector<int>(Size , 2);

void Make_MAP(vector<vector<int>> lock)
{
	int lock_x = 0;
	int lock_y = 0;
	for (int i = M - 1; i < Size - (M - 1); i++, lock_x++)
	{
		for (int j = M - 1; j < Size - (M - 1); j++, lock_y++)
		{
			MAP[i][j] = lock[lock_x][lock_y];
			if (MAP[i][j] == 0) Point++;
		}
		lock_y = 0;
	}
}

 

#4. 열쇠 맞추기

이제 #2와 #3에서 공들여 만든 새로운 맵에서 열쇠를 움직이면서 맞춰보기만 하면 된다.

핵심적으로 생각해 주어야 할 것은, 어디까지 움직여 줘야하는지만 생각을 해보면 된다.

위의 그림을 봐보자. 딱 봐도 열쇠가 저기 우측 빨강색 사각형까지 움직이면 안될 것이다.

즉 ! 최대로 움직일 수 있는 칸은 위의 그림과 같다는 것이다.

빨강색 사각형이 움직인 칸수를 보면 움직일 수 있는 칸수는 총 5칸이라는 것을 알 수 있다.

M = 3 , N = 3 일 때, 5칸을 움직인다는 것이다.

즉 ! 열쇠가 움직일 수 있는 칸수는 "M + N - 1" 칸이 된다.

 

움직이면서 비교를 해봐야 할 것은 무엇일까 ?? 다음과 같은 조건들을 비교해 보면 될 것이다.

1. 큰 맵에서의 데이터가 돌기이고, 열쇠에서의 데이터가 돌기인 경우

2. 큰 맵에서의 데이터가 홈이고, 열쇠에서의 데이터가 홈인 경우

3. 큰 맵에서의 데이터가 홈이고, 열쇠에서의 데이터가 돌기인 경우

1, 2번 같은 경우에는 더 이상의 탐색을 해볼 필요도 없이 잘못된 경우이다.

왜냐하면, 돌기와 돌기가 만나면 안되고, 홈과 홈이 만나면 자물쇠의 홈을 채울 수 없음을 의미하기 때문에 잘못된 경우이다. 3번 같은 경우에는 올바르게 탐색을 하고 있는 경우이다.

이 부분을 코드로 나타내면 다음과 같다.

int Sum_Key_And_Lock(int Sx, int Sy, vector<vector<int>> key)
{
	int x_Idx = 0;
	int y_Idx = 0;
	int Check = 0;
	for (int x = Sx; x < Sx + M; x++, x_Idx++)
	{
		for (int y = Sy; y < Sy + M; y++, y_Idx++)
		{
			if (MAP[x][y] == 1 && key[x_Idx][y_Idx] == 1) return -1;
			if (MAP[x][y] == 0 && key[x_Idx][y_Idx] == 0) return -1;
			if (MAP[x][y] == 0 && key[x_Idx][y_Idx] == 1) Check++;
		} 
		y_Idx = 0;
	}
	return Check;
}

본인은, 열쇠의 돌기가 자물쇠의 홈을 만날 때 마다 Count를 위한 변수를 하나 만들어서 그 갯수를 Count 해주었다.

결과적으로, 기존의 자물쇠에 있는 홈의 갯수와, 열쇠의 돌기와 자물쇠의 홈이 만난 갯수를 비교해서 같다면, 자물쇠의 모든 홈을 열쇠의 돌기가 채웠음을 의미하고, 이 경우에는 자물쇠를 열 수 있다는 것을 의미한다.

이를 통해서 자물쇠를 열 수 있는지를 판단해 주었다.

 

#5. 회전하기

이제 마지막으로 열쇠를 회전하는 과정을 진행해보자.

간단하게, 3 x 3 크기의 열쇠로 알아보자.

위의 사각형을 시계방향으로 회전시킨다면, 좌표의 변화는 다음과 같을 것이다.

A의 자리에는 'G'가 , B의 자리에는 'D'가, C의 자리에는 'A'가 오게 될 것이다.

이를 좌표로 나타내보면...

(0 , 0)의 자리에는 (2 , 0)의 데이터가

(0 , 1)의 자리에는 (1 , 0)의 데이터가

(0 , 2)의 자리에는 (0 , 0)의 데이터가 오게 될 것이다.

 

D의 자리에는, 'H'가 , G의 자리에는 'I'가 오게 될 것이다.

이를 좌표로 나타내보면...

(1 , 0)의 자리에는 (2 , 1)의 데이터가

(2 , 0)의 자리에는 (2 , 2)의 데이터가 오게 된다.

이 5개의 데이터를 토대로 정리해보자.

 

(0 , 0) - (2 , 0)

(0 , 1) - (1 , 0)

(0 , 2) - (0 , 0)

(1 , 0) - (2 , 1)

(2 , 0) - (2 , 2)

(x , y) - (A , B)

먼저, 'B'에 들어오는 값은 쉽게 눈치챌 수 있을 것이다.

바로, 'x'가 들어오게 된다.

그럼 'A'에는 무슨 값이 들어가게 될까 ??

바로, M - 1 - y의 값이 들어오게 된다.

(0 , 0)에서 x좌표인 '0'이 '2'가 되는 것은, 전체 길이인 3 에서 1을 빼고, y좌표인 '0'을 뺀 것이 되는 것이다.

(0 , 1)에서 x좌표인 '0'이 '1'이 되는 것은, 전체 길이인 3 에서 1을 빼고, y좌표인 '1'을 뺀 것이 되는 것이다.

즉, (x , y) = (M - 1 - y , x) 가 되는 것이 이 맵을 회전시킨 것과 동일한 효과를 가지게 된다.

이 부분을 코드로 나타내보면 다음과 같다.

void Rotate_Key(vector<vector<int>> &Key)
{
	//(0 , 0)에는 (2 , 0)의 값이
	//(0 , 1)에는 (1 , 0)의 값이
	//(0 , 2)에는 (0 , 0)의 값이
	//(1 , 0)에는 (2 , 1)의 값이
	//(x , y)에는 (M - 1 - y , x)의 값이
	vector<vector<int>> Temp = Key;
	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < M; j++)
		{
			Temp[i][j] = Key[M - 1 - j][i];
		}
	}
	Key = Temp;
}

 

이 모든 과정을 진행을 하게 되면 정답을 구할 수가 있다.

또한, 회전은 한번만 하는 것이 아닌 90도, 180도, 270도, 360도 까지 회전을 해봐야 하므로 총 4가지 상태에 대해서 탐색을 해봐야 한다.

 

[ 소스코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
int M, N, Size, Point;
vector<vector<int>> MAP;
 
void Make_MAP(vector<vector<int>> lock)
{
    int lock_x = 0;
    int lock_y = 0;
    for (int i = M - 1; i < Size - (M - 1); i++, lock_x++)
    {
        for (int j = M - 1; j < Size - (M - 1); j++, lock_y++)
        {
            MAP[i][j] = lock[lock_x][lock_y];
            if (MAP[i][j] == 0) Point++;
        }
        lock_y = 0;
    }
}
 
int Sum_Key_And_Lock(int Sx, int Sy, vector<vector<int>> key)
{
    int x_Idx = 0;
    int y_Idx = 0;
    int Check = 0;
    for (int x = Sx; x < Sx + M; x++, x_Idx++)
    {
        for (int y = Sy; y < Sy + M; y++, y_Idx++)
        {
            if (MAP[x][y] == 1 && key[x_Idx][y_Idx] == 1) return -1;
            if (MAP[x][y] == 0 && key[x_Idx][y_Idx] == 0) return -1;
            if (MAP[x][y] == 0 && key[x_Idx][y_Idx] == 1) Check++;
        } 
        y_Idx = 0;
    }
    return Check;
}
 
void Rotate_Key(vector<vector<int>> &Key)
{
    //(0 , 0)에는 (2 , 0)의 값이
    //(0 , 1)에는 (1 , 0)의 값이
    //(0 , 2)에는 (0 , 0)의 값이
    //(1 , 0)에는 (2 , 1)의 값이
    //(x , y)에는 (M - 1 - y , x)의 값이
    vector<vector<int>> Temp = Key;
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < M; j++)
        {
            Temp[i][j] = Key[M - 1 - j][i];
        }
    }
    Key = Temp;
}
 
bool Move_MAP(vector<vector<int>> key)
{
    for (int R = 0; R < 4; R++)
    {
        for (int i = 0; i < M + N - 1; i++)
        {
            for (int j = 0; j < M + N - 1; j++)
            {
                int Result = Sum_Key_And_Lock(i, j, key);
                if (Result == Point) return true;
            }
        }
        Rotate_Key(key);
    }
    return false;
}
 
bool solution(vector<vector<int>> key, vector<vector<int>> lock)
{
    // M = M , N = N인 경우에
    // 가로, 세로 길이 = N + (M - 1) + (M - 1) = N + 2 * (M + 1)
    M = key.size();
    N = lock.size();
    Size = N + 2 * (M - 1);
    MAP.resize(Size, vector<int>(Size, 2));
    Make_MAP(lock);
    bool answer = Move_MAP(key);
    return answer;
}