[ 2020 KAKAO BLIND RECRUITMENT ] 자물쇠와 열쇠

 

 

  CatServant  

 문제 풀이

 

위의 그림과 같이 주위에 zero padding을 주고 Lock의 모든 좌표를 확인하면서 진행하면 된다.

그 과정을 key를 90도 씩 회전하면서 4번을 반복하는데 Lock과 Key가 딱 맞아 떨어지는 경우 Ture를 return 해준다. 그런데 이 때, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 key의 돌기와 Lock의 돌기가 만나서는 안된다!

2가지 사항만 기억하면 크게 어려운 문제는 아니다.

 

 Code

#include <iostream>
#include <vector>

using namespace std;

int lockBoard[60][60];
int rotakey[20][20];
int copyBoard[60][60];

void clearBoard(int lockSZ) {
	for (int r = 20; r < 20+lockSZ; r++) {
		for (int c = 20; c < 20 + lockSZ; c++) {
			copyBoard[r][c] = lockBoard[r][c];
		}
	}
}

bool isCorrect(int lockSZ) {
	for (int r = 20; r < 20 + lockSZ; r++) {
		for (int c = 20; c < 20 + lockSZ; c++) {
			if (copyBoard[r][c] == 0)
				return false;
		}
	}
	return true;
}

bool CompareBoard(int keySz, int lockSz) {
	for (int r = 20 - (keySz-1); r < 20 + lockSz; r++) {
		for (int c = 20 - (keySz - 1); c < 20 + lockSz; c++) {
			clearBoard(lockSz);
			for (int kr = 0; kr < keySz; kr++) {
				for (int kc = 0; kc < keySz; kc++) {
					if ((r + kr >= 20 
						&& r + kr < (20+lockSz) 
						&& c + kc >= 20 
						&& c + kc < (20 + lockSz))) {
						
						if (copyBoard[r + kr][c + kc] == rotakey[kr][kc])
							goto HERE;
						else
							copyBoard[r + kr][c + kc] = 1;
					}
				}
			}
		HERE:
			if (isCorrect(lockSz))
				return true;
		}
	}
	return false;
}

void RotateKey(int sz) {
	int temp[20][20];

	for (int j = 0; j < sz; j++)
		for (int i = 0; i < sz; i++)
			temp[i][sz - 1 - j] = rotakey[j][i];


	for (int j = 0; j < sz; j++)
		for (int i = 0; i < sz; i++)
			rotakey[j][i] = temp[j][i];
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
	int sz = key.size();
	int lsz = lock.size();
	int sr = 20 , sc = 20;
	

	for (int j = 0; j < lsz; j++) {
		for (int i = 0; i < lsz; i++) {
			lockBoard[j + sr][i + sc] = lock[j][i];
		}
	}

	for (int j = 0; j < sz; j++) {
		for (int i = 0; i < sz; i++) {
			rotakey[j][i] = key[j][i];
		}
	}

	for (int idx = 0; idx < 4; idx++) {
		if (CompareBoard(sz, lsz))
			return true;
		
		RotateKey(sz);
	}

	return false;
}

int main() {
	ios_base::sync_with_stdio(false);

	vector<vector<int> > key = {
		{0, 0, 0},
		{1, 0, 0},
		{0, 1, 1}
	};

	vector<vector<int> > lock = {
		{1, 1, 1},
		{1, 1, 0},
		{1, 0, 1}
	};

	cout << solution(key, lock);

	return 0;
}

 

 

출처

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

프로그래머스