[프로그래머스] Level 3: 자물쇠와 열쇠

https://school.programmers.co.kr/learn/courses/30/lessons/60059

프로그래머스

 

키(Key)보다 자물쇠(Lock)의 배열이 더 클 수 있음에 유의하자.

 

키를 이동 & 회전시켜서 자물쇠에 모든 홈이 채워지게 해야 한다.

즉, 자물쇠 배열이 모두 1이 되어야 한다.

 

자물쇠(Lock) 비교 조건

• 자물쇠(Lock)의 해당 칸이 1인가? 1이라면, 해당 칸의 키(Key)는 0이어야 한다.
• 자물쇠(Lock)의 해당 칸 칸이 1인데, 키(Key)도 1이라면 실패다.
  • 단, 키(Key)가 자물쇠(Lock) 크기보다 작을 수 있기 때문에, 바로 리턴하지 말고 반드시 가능한 배치를 모두 검사해야 한다.

예를 들어, 어떤 키(Key)를 이동 & 회전시켜 다음과 같은 자물쇠(Lock) 비교 상황이 되었다고 하자.

해당 키(Key)를 통해서는 자물쇠(Lock)를 다음과 같이 4번 배치할 수 있다.

만약, 1번 배치에서 맞지 않다고 해서 리턴해버리면, 2번, 3번, 4번은 검사하지 않았기 때문에 오류가 날 수 있다.

• 키(Key) 배열이 모두 0이고, 자물쇠(Lock) 배열이 모두 1인 경우여도 모든 홈을 채운 것과 같기 때문에, true이다.

결론적으론, 키(Key)와 자물쇠(Lock)의 돌기가 맞닿지 않으며, 자물쇠(Lock)의 모든 홈을 채우는 것이다.

먼저 자물쇠(Lock)를 순회하여 채워야 할 홈이 몇 개인지 확인한다.

자물쇠(Lock) 비교에서, 모두 순회했는데 돌기가 맞닿은 적이 없으며, 모든 홈을 채웠다면, true를 반환한다.

 

 

키(Key) 확장 배열 이동

모든 경우의 수를 순회하며 찾아야 한다.

배열의 크기가 3 <= n <= 20이므로, 최악의 상황이어도 시간이 많이 걸리지 않는다.

 

키(Key)를 이동할 수 있는 모든 경우로 이동한다고 해보자.

한 칸이라도 기존 키(Key)의 값을 가져오려면 최대 key.size() + (key.size()  - 1) * 2칸까지 배열을 확장할 수 있다.

 

이렇게 확장시킨 배열은, 다음과 같이 기존의 키(Key)가 이동할 수 있는 모든 배치를 가지고 있다.

이를 하나씩 자물쇠(Lock)와 비교한다.

 

 

키(Key) 확장 배열 회전

이제 키(Key)가 회전한 경우도 구해보자.

앞서 확장한 키(Key) 확장 배열을 그대로 가지고, 기존 키(Key) 부분인 가운데 부분만 회전시키면 된다.

이렇게 회전된 키(Key)를 원본 키로 초기화하고, 다시 처음부터 검사를 수행하면 된다.

 

최종 로직 순서

1. 기존 키(Key) -> 키(Key) 확장 배열 초기화
2. 키(Key) 확장 배열을 기반으로 이동할 수 있는 모든 위치에서 비교할 부분만 떼어내 새 키(Key) 생성
3. 자물쇠(Lock) 비교
   • 키(Key) 배열이 자물쇠(Lock) 배열보다 작을 수 있으므로, 자물쇠(Lock) 배열 내에서도 키(Key) 배열을 모두 검사할 수 있도록 배치하여 비교
4. true가 안 나왔을 경우, 자물쇠(Lock) 회전
5. 2번 ~ 4번 반복

#include <string>
#include <vector>
using namespace std;

bool Func(const vector<vector<int>>& Key, const vector<vector<int>>& lock, int Sy, int Sx, const int N, const int LockHole)
{
	int Size = N + 1;

	// 키(Key) 확장 배열에서 검사할 부분만 떼어내 새 키(key) 생성
	vector<vector<int>> NewKey(Size, vector<int>(Size, 0));
	for (int y = 0, sy = Sy; y < Size; ++y, ++sy)
		for (int x = 0, sx = Sx; x < Size; ++x, ++sx)
			NewKey[y][x] = Key[sy][sx];

	// 자물쇠와 비교
	for (int y = 0; y <= lock.size() - Size; ++y)
	{
		for (int x = 0; x <= lock.size() - Size; ++x)
		{
			bool Check = true;
			int Count = 0;

			for (int yy = 0; yy < Size; ++yy)
			{
				for (int xx = 0; xx < Size; ++xx)
				{
					if (lock[yy + y][xx + x] == 1 && NewKey[yy][xx] == 0) continue;
					else if (lock[yy + y][xx + x] == 1 && NewKey[yy][xx] == 1) { Check = false; break; }
					else if (lock[yy + y][xx + x] == 0 && NewKey[yy][xx] == 1) Count++;
				}
			}
			if (Check && Count == LockHole) return true;
		}
	}

	return false;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock)
{
	int N = key.size() - 1;

	// 채워야하는 자물쇠의 홈
	int LockHole = 0;
	for (const auto& i : lock)
		for (const auto& j : i)
			if (j == 0) LockHole++;

	// 확장 배열 초기화 (Key가 이동할 수 있는 최대 반경)
	vector<vector<int>> Key(key.size() + (N * 2), vector<int>(key.size() + (N * 2), 0));
	for (int y = N, keyY = 0; y < key.size() + N; ++y, ++keyY)
		for (int x = N, keyX = 0; x < key.size() + N; ++x, ++keyX)
			Key[y][x] = key[keyY][keyX];

	for (int i = 0; i < 4; ++i)
	{
		// 이동할 수 있는 모든 경우에서 이동하며 검사
		for (int y = 0; y < key.size() + N; ++y)
			for (int x = 0; x < key.size() + N; ++x)
				if (Func(Key, lock, y, x, N, LockHole)) return true;


		// 키(Key) 확장 배열 회전
		vector<vector<int>> NewKey(key.size() + (N * 2), vector<int>(key.size() + (N * 2), 0));

		for (int y = N; y <= N * 2; ++y)
			for (int x = N, yy = N * 2; x <= N * 2; ++x, --yy)
				NewKey[y][x] = Key[yy][y];

		Key = NewKey;
	}

	return false;
}