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

문제 바로가기

코딩테스트 연습 - 자물쇠와 열쇠

완전탐색 문제.

백트래킹으로 풀려고 하다가 이상해가지고 ㅠ,, 그냥 완탐으로 풀면 되는 문제였당 

근데 그것도 쉽지않았다

자물쇠 열쇠 배열 크기가 다를 수도 있는데 예시 테케가 같아가지고 그냥 아무생각 없이 같다고 두고 풀었당.. 개멍충이

 

<문제 풀이 Logic>

자물쇠 배열의 크기 N, 열쇠 배열의 크기 M이라고 할 때,

새로운 자물쇠 배열을 N + 2 * (M-1) size로 지정해준다. 

그리고 열쇠 배열을 옮겨가면서 새로운 자물쇠 배열 위에서 옮겨주며 XOR 연산을 한다. 이 때 기존의 자물쇠 배열 부분만 뽑아서 (index: M-1 ~ N + (M-1)까지) 배열의 원소가 모두 1인지 확인해준다. -> 1이여야만 자물쇠의 홈과 열쇠의 돌기가 맞아떨어지는 경우이다.

 

 

-전체 코드-

#include <string>
#include <vector>
#include <iostream>

using namespace std;
int N, M;
bool answer = false;
int empty_lock;
int pos[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };

bool isIn(int y, int x)
{
	if (y >= 0 && y < M && x >= 0 && x < M)
		return true;
	return false;
}

vector<vector<int>> rotate(vector<vector<int>> tmp, int size)
{
	for (int i = 0; i < size / 2; i++)
		for (int j = i; j < size - 1 - i; j++)
		{
			int Top = tmp[i][j]; // Top ← 위쪽

			tmp[i][j] = tmp[size - 1 - j][i]; // 위쪽 ← 왼쪽

			tmp[size - 1 - j][i] = tmp[size - 1 - i][size - 1 - j]; // 왼쪽 ← 아래쪽

			tmp[size - 1 - i][size - 1 - j] = tmp[j][size - 1 - i]; // 아래쪽 ← 오른쪽

			tmp[j][size - 1 - i] = Top; // 오른쪽 ← Top(위쪽)
		}

	return tmp;
}

bool isCorrect(vector<vector<int>> key, vector<vector<int>> lock, int y_start, int x_start)
{

	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < M; j++)
		{
			lock[i + y_start][j + x_start] = lock[i + y_start][j + x_start] ^ key[i][j];
		}
	}

	for (int i = 0; i < 2 * (M- 1) + N; i++)
	{
		for (int j = 0; j < 2 * (M - 1) + N; j++)
		{
			cout << lock[i][j] << " ";
		}
		cout << endl;
	}

	for (int i = M - 1; i < N + (M - 1); i++)
	{
		for (int j = M - 1; j < N + (M - 1); j++)
		{
			if (lock[i][j] == 0)
				return false;
		}
	}
	return true;
}


bool solution(vector<vector<int>> key, vector<vector<int>> lock) {

	M = key.size();
	N = lock.size();

	vector<vector<int>> total_lock(2 * (M - 1) + N, vector<int>(2 * (M - 1) + N, 0));

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			total_lock[i + (M - 1)][j + (M - 1)] = lock[i][j];
		}
	}

	/*for (int i = 0; i < 2 * (N - 1) + N; i++)
	{
		for (int j = 0; j < 2 * (N - 1) + N; j++)
		{
			cout << total_lock[i][j] << " ";
		}
		cout << endl;
	}*/

	for (int i = 0; i < N + (M-1); i++)
	{
		for (int j = 0; j < N + (M-1); j++)
		{
			int y_start = i;
			int x_start = j;

			vector<vector<int>> new_key(N, vector<int>(N,0));

			for (int p = 0; p < 4; p++)//회전: 0번, 1번, 2번, 3번
			{

				for (int y = 0; y < M; y++)
				{
					for (int x = 0; x < M; x++)
					{
						cout << key[y][x] << " ";
					}
					cout << endl;
				}

				cout << "---------------"<< endl;

				if (isCorrect(key, total_lock, y_start, x_start))
				{
					answer = true;
					cout << answer;
					return answer;
				}


				key = rotate(key, key.size());

				cout << endl;
			}
		}
	}

	cout << answer;
	return answer;
}

int main()
{
	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} };


	solution(key, lock);

	return 0;
}