[프로그래머스/20년 카카오 블라인드] 자물쇠와 열쇠(Lv.3), C++

자물쇠와 열쇠(링크)

문제에서 주어지는 key, lock 은 기껏해야 20 x 20 크기의 2차원 배열이다. 따라서 key 를 lock 위에 겹치도록 한 뒤 겹친 칸의 값을 더해보고 lock 의 모든 칸이 1 이 되었는지 확인하면 된다. 이 과정을 key 배열을 90도씩 회전해가며 모두 검사하기에도 충분한 입력이다.

 

아래 그림과 같이 겹치기 시작해서

 

 

아래 그림처럼 마지막 칸이 겹칠 때까지 key 배열이 lock 배열 위를 순회하도록 한다. 그림에서 볼 수 있듯이 lock 배열의 영역 밖으로 나가는 key 배열의 칸들이 있고 key 값을 lock 과 더하는 과정에서 영역 밖 위치의 접근이 일어나기 때문에 lock 배열에 padding 을 두면 편하다.

 

 

padding 은 필요한 만큼만 덧붙이면 되는데 key 가 최소한 1 칸이 겹친 상태에서 순회를 시작하므로 (key 의 한 변의 길이 - 1) 만큼의 padding 이 lock 의 상하좌우로 필요하다.

 

typedef vector<vector<int>> vvi;

vvi rotate(vvi v, int n) {
	vvi ret(v);
	int size = v.size();

	while (n--) {
		for (int i = 0; i < size; ++i) 
			for (int j = 0; j < size; ++j) 
				ret[j][size - 1 - i] = v[i][j];
		v = ret;
	}

	return ret;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
	bool answer;
	int lSize = lock.size(), kSize = key.size();
	int pad = kSize - 1;

	// Initialize a padding lock vector.
	vvi padLock(lSize + 2 * pad, vector<int>(lSize + 2 * pad, 0));
	for (int i = 0; i < lSize; ++i) 
		for (int j = 0; j < lSize; ++j) 
			padLock[i + pad][j + pad] = lock[i][j];

	for (int r = 0; r < 4; ++r) {
		// Rotating key 90 degrees clockwise for r times.
		vvi rotKey = rotate(key, r);

		// Iterate the padding lock vector.
		int lr, lc, kr, kc;
		for (lr = 0; lr < lSize + pad; ++lr) {
			for (lc = 0; lc < lSize + pad; ++lc) {

				// Match the key and the lock.
				for (kr = 0; kr < kSize; ++kr)
					for (kc = 0; kc < kSize; ++kc)
						padLock[lr + kr][lc + kc] += rotKey[kr][kc];

				// Checking answer.
				answer = true;
				for (int i = 0; i < lSize; ++i) 
					for (int j = 0; j < lSize; ++j)
						if (padLock[i + pad][j + pad] != 1) answer = false;
				if (answer) return true;

				// Unmatch the key and the lock.
				for (kr = 0; kr < kSize; ++kr)
					for (kc = 0; kc < kSize; ++kc)
						padLock[lr + kr][lc + kc] -= rotKey[kr][kc];
			}
		}
	}

	return answer;
}