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

링크

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

코딩테스트 연습 - 자물쇠와 열쇠 | 프로그래머스

풀이

자물쇠 구멍에 맞는 알맞은 열쇠의 모습을 구하는 문제 인데.

 

열쇠를 4방향으로 돌려 본 후 좌물쇠를 탐색하는 방식으로 문제를 풀었습니다.

이때 좌물쇠와 열쇠를 딱 알맞게 맞추어야 하지 않아도 되기 때문에

열쇠로 좌물쇠를 탐색할 범위를 (좌물쇠의 크기 *3 -2) by (좌물쇠의 크기 *3 -2)로 정했습니다.

 

이제 열쇠 돌기와 좌물쇠의 홈이 알맞게 맞는지 카운트 하고, 하지만 자물쇠의 돌기와 열쇠의 돌기가 만나면 탐색을 종료 하도록 하였습니다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>

#define SIZE 100
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

int board[SIZE][SIZE];
int lock_cnt;
int lock_check(vector<vector<int>> &lock) {
	int cnt = 0;
	int lock_size = lock.size();
	for (int i = 0; i < lock_size;i++) {
		for (int j = 0; j < lock_size; j++) {
			if (lock[i][j] == 0) {
				cnt++; lock[i][j] = 2;
			}
			board[lock_size - 1 + i][lock_size - 1 + j] = lock[i][j];
		}
	}

	return cnt;
}
void r(vector<vector<int>> &key) {
	int m = key.size();
	vector<vector<int>> temp(m, vector<int>(m, 0));
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			//temp[i][j] = key[j][m - i - 1];
			temp[i][j] = key[m - j - 1][i];
		}
	}
	key = temp;
}

bool check(vector<vector<int>> key,int i, int j) {
	int correct = 0;
	int key_size = key.size();
	for (int d = 0; d < 4; d++) {
		r(key);
		correct = 0;
		for (int ki = 0, li = i; ki < key_size; ki++, li++) {
			for (int kj = 0, lj = j; kj < key_size; kj++, lj++) {
				if (key[ki][kj]==1 && board[li][lj]==1) {
					break;
				}
				if (key[ki][kj] == 1 && board[li][lj] == 2)
					correct++;
			}
		}
		if (correct == lock_cnt) {
			return true;
		}
	}
	return false;

}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
	lock_cnt = lock_check(lock);
	int lock_size = lock.size();
	int size = lock_size * 3 - 2;
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			if (check(key, i, j))
				return true;
		}

	}
	return false;
}