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

2020 KAKAO BLIND RECRUITMENT (2020 카카오 블라인드 채용 문제)

Key를 회전시키거나 움직여서 Lock의 빈 부분을 모두 채우는 문제입니다.

Lock를 90도로 회전시켜서 4개의 Lock를 생성하였습니다. (0도, 90도, 180도, 270도)
Key를 4개의 Lock에 XOR연산자를 이용해서 맞추어봅니다.

XOR연산자 대신 if문으로 처리도 가능합니다. 두개가 다를 경우를 체크하기 때문에 XOR연산자를 사용했습니다.

(Lock - 0, Key - 0 이면 홈이 없는상태, Lock - 1, Key - 1 두 부분다 홈인 경우)
(Lock - 1, Key - 0 홈이 맞는 상태 Lock - 0, Key - 1 홈이 맞는 상태)

탐색 과정

Key	Key	Key
Key	Key	Key
Key	Key	Key Lock	Lock	Lock
		Lock	Lock	Lock
		Lock	Lock	Lock

 

	Key	Key	Key
	Key	Key	Key
	Key	Key Lock	Key Lock	Lock
		Lock	Lock	Lock
		Lock	Lock	Lock

 

		Key Lock	Key Lock	Key Lock
		Key Lock	Key Lock	Key Lock
		Key Lock	Key Lock	Key Lock

 

		Lock	Lock	Lock
		Lock	Lock	Lock
		Lock	Lock	Lock Key	Key	Key
				Key	Key	Key
				Key	Key	Key

 

위의 이미지에서와 같이 Key를 이동해서 모든 부분을 탐색합니다. 그리고 Lock과 맞는지 확인합니다.

 

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;

vector<vector<vector<int>>> globalLock;

void rotate()
{
  vector<vector<int>> lock(globalLock[0]);
  int lockLen = lock.size();

  int count = 1;
  while (count <= 3)
  {
    for (int i = 0; i < lockLen / 2; ++i)
    {
      for (int j = i; j < lockLen - 1 - i; ++j)
      {
        int Top = lock[i][j];

        lock[i][j] = lock[lockLen - 1 - j][i];
        lock[lockLen - 1 - j][i] = lock[lockLen - 1 - i][lockLen - 1 - j];
        lock[lockLen - 1 - i][lockLen - 1 - j] = lock[j][lockLen - 1 - i];
        lock[j][lockLen - 1 - i] = Top;
      }
    }
    globalLock.push_back(lock);
    ++count;
  }
}

bool func(vector<vector<int>> key, int y, int x, int n)
{
  vector<vector<int>> check = globalLock[n];
  int keyLen = key.size();
  int lockLen = check.size();

  for (int i = 0; i < lockLen; ++i)
  {
    for (int j = 0; j < lockLen; ++j)
    {
      if (y + i >= 0 && x + j >= 0 && y + i < keyLen && x + j < keyLen)
      {
        if (check[i][j] + key[y + i][x + j] ^ 1)
        {
          return false;
        }
      }
      else if (check[i][j] == 0)
      {
        return false;
      }
    }
  }
  return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock)
{
  globalLock.push_back(lock);

  rotate();
  int keyLen = key.size();
  int lockLen = lock.size();

  for (int i = -lockLen + 1; i < keyLen; ++i)
  {
    for (int j = -lockLen + 1; j < keyLen; ++j)
    {
      if (func(key, i, j, 0))
      {
        cout << true << endl;
        return true;
      };
      if (func(key, i, j, 1))
      {
        cout << true << endl;
        return true;
      };
      if (func(key, i, j, 2))
      {
        cout << true << endl;
        return true;
      };
      if (func(key, i, j, 3))
      {
        cout << true << endl;
        return true;
      };
    }
  }
  cout << false << endl;
  return false;
}