[Programmers] 자물쇠와 열쇠 - travelbeeee

문제 : 2020 카카오 BLINE RECRUITMENT 자물쇠와 열쇠

---

구현

● 열쇠를 돌리고 옮겨가며 자물쇠와 맞는지 안맞는지 체크하면 된다.

● 열쇠는 기존의 상태, 90도 회전 상태, 180도 회전 상태, 270도 회전 상태 총 4가지 모양을 가질 수 있고, 기존의 상태부터 옮겨가며 현재 자물쇠와 맞는지 안맞는지 체크하고, 90도 회전한 후 다시 옮겨가며 현재 자물쇠와 맞는지 안맞는지 체크하고, 90도 더 회전한 후 다시 옮겨가며 체크하는 과정을 반복하면 된다.

● 열쇠를 회전하는 과정은 열쇠 배열을 그대로 복사한 후, 다음과 같은 식으로 회전해서 덮으면 된다.

for (int i = 0; i < N; i++)
	for (int j = 0; j < N; j++)
		key[i][j] = tempKey[N - 1 - j][i];

● 열쇠를 옮겨가며 자물쇠와 맞는지 안맞는지 체크하는 부분이 문제의 핵심인데, 열쇠랑 자물쇠가 한 칸이라도 겹치는 모든 (i , j) 에서 N x N 크기의 열쇠를 그리고 자물쇠와 겹치는 부분을 체크해주면 된다.

아래 그림과 같이 열쇠를 한 칸씩 이동해가며 모든 경우에 대해 자물쇠와 열쇠의 상태를 확인해주면 됩니다.

● 열쇠가 0인 부분은 자물쇠가 0이던 1이던 상관이 없고, 열쇠가 1일 때 자물쇠가 0이면 우리가 원하는 상황이고, 열쇠가 1일 때 자물쇠가 1이면  문제가 발생하므로 (열쇠, 자물쇠) 가 (1, 0) 이면 자물쇠의 상태를 1로 바꿔주고, (1, 1) 이면 자물쇠의 상태를 0으로 바꿔준다. 

#include <string>
#include <vector>

using namespace std;

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
	int rotation = 0, N = key.size(), M = lock.size();
	do {
		// check
		for (int i = -N + 1; i < M; i++) {
			for (int j = -N + 1; j < M; j++) {
				// (i , j) 에서 N x N key를 그린다고 생각.
				vector<vector<int>> tempLock(M);
				for (int k = 0; k < M; k++)
					for (int l = 0; l < M; l++)
						tempLock[k].push_back(lock[k][l]);

				for (int k = 0; k < N; k++) {
					for (int l = 0; l < N; l++) {
						if (0 <= (i + k) && (i + k) < M && 0 <= (j + l) && (j + l) < M) {
							if (tempLock[i + k][j + l] == 0 && key[k][l] == 1)
								tempLock[i + k][j + l] = 1;
							else if (tempLock[i + k][j + l] == 1 && key[k][l] == 1)
								tempLock[i + k][j + l] = 0;
						}
					}
				}
				// 제대로 만들어졌는지 체크하자.
				bool tempCheck = true;
				for (int k = 0; k < M; k++)
					for (int l = 0; l < M; l++)
						if (tempLock[k][l] == 0)
							tempCheck = false;
				if (tempCheck == true)
					return true;
			}
		}
		// 회전
		vector<vector<int>> tempKey(N);
		for (int i = 0; i < N; i++) 
			for (int j = 0; j < N; j++)
				tempKey[i].push_back(key[i][j]);
		for (int i = 0; i < N; i++) 
			for (int j = 0; j < N; j++) 
				key[i][j] = tempKey[N - 1 - j][i];

		rotation++;
	} while (rotation < 4);

	return false;
}

---