[프로그래머스][C++] 2020 KAKAO: 자물쇠와 열쇠

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/60059

 

구현 문제입니다. 2020 kakao blind recruitment 문제이고요

여러가지 방식이 있겠지만 저는 열쇠 돌기들의 좌표를 vector에 넣고, 자물쇠를 90도씩 돌린 다음에 자물쇠의 모든 홈에 돌기가 들어갈 수 있는 경우의 수를 전부 만들어서 홈이 전부 메꿔지면 true, 홈이 전부 메꿔지지 않거나 열쇠의 돌기와 자물쇠의 돌기가 만나면 false를 반환했습니다.

M과 N 크기가 20 이하로 작기 때문에 완전탐색이 가능합니다. 제 알고리즘의 경우 대충 \(O(N^2 d^2)~\text{(d=열쇠 돌기의 수)}\) 이 정도의 시간복잡도가 나오는 것 같네요.

 

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

void rotate90(vector<vector<int>>& arr) {
  const int& sz = arr.size();
  vector<vector<int>> new_arr(sz);
  for (auto& v : new_arr)
    v.resize(sz);

  for (int i = 0; i < sz; ++i) {
    for (int j = 0; j < sz; ++j) {
      new_arr[j][sz - i - 1] = arr[i][j];
    }
  }

  arr = move(new_arr);
}

bool in_range(const int& n, const int& y, const int& x) {
  return (y>=0 && y<n && x>=0 && x<n);
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
  const int& M = key.size();  // 열쇠 한 변의 길이
  const int& N = lock.size(); // 자물쇠 한 변의 길이
  
  int dolki;    // 열쇠 돌기의 개수
  int hom = 0;  // 자물쇠 홈의 개수

  vector<pair<int, int>> vp;
  for (int i = 0; i < M; ++i) {
    for (int j = 0; j < M; ++j) {
      if (key[i][j] == 1) {
        vp.emplace_back(i, j);
      }
    }
  }
  dolki = vp.size();

  
  for (auto& v : lock)
    for (auto& c : v)
      if (c == 0)
        ++hom;

  // 예외처리
  if (hom > dolki)  return false; // 홈이 돌기보다 많은 경우
  if (hom == 0)   return true;  // 홈이 0개
  if (dolki == 0)   return false; // 돌기가 0개

  
  for (int turn = 0; turn < 4; ++turn) {
    if (turn != 0)
      rotate90(lock);

    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        if (lock[i][j] == 0) {
          for (int first = 0; first < dolki; ++first) {
            int match_cnt = 1;
          
            for (int k = 0; k < dolki; ++k) {
              if (k == first) continue;

              auto y = (vp[k].first - vp[first].first) + i;
              auto x = (vp[k].second - vp[first].second) + j;
              if (in_range(N, y, x)) {
                if (lock[y][x]==0)
                  ++match_cnt;
                else {  //돌기와 돌기가 만날 때
                  match_cnt = -99999;
                  break;
                }
              }
            }
          
            if (match_cnt == hom) return true;
          }
        }
      }
    }
  }

  return false;
}

int main()
{
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
#endif

  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  /*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} };*/

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

  cout << solution(key, lock) << '\n';

  return 0;
}