⚙️ 알고리즘 분류 : 구현
🔠 언어 : c++
🤫 힌트.
그냥 문제에서 하란 대로. 직관적으로 풀면 된다.
✏️ 풀이.
그냥 문제에서 하란 대로 하면 된다. 문제를 보면 회전과 이동을 하라고 써져있는데, 회전을 구현하고 이동을 구현하면 된다.
⬇️ 회전 Algorithm
// 3*3 격자판에 (1,2) 점이 회전을 하면
// (1,2) -> (2,3) -> (3,2) -> (2,1)
// (2,3) 입장에선 (1,2)를 가져와야 하는데, 2는 그대로 가져오면 되고
// 1은 {3-(격자판 길이)+1}와 같다. 생각 좀 하면 만들 수 있는 알고리즘!
for(int i=0; i<m; i++){
for(int j=0; j<m; j++){
tmp[i][j]=key[m-1-j][i];
}
}그리고 2*m+n 길이의 격자판이 필요하다. 필요한 이유는 문제에 있다.
문제에서 '자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만'이라는 부분이 있다.
key를 lock의 범위가 벗어나게끔 맞춰도 상관 없다는 뜻이다.
즉, key가 lock의 범위에 걸칠 수 있는 최소 영역은 상단왼쪽 or 하단오른쪽 모서리 1칸.
그래서 n에서 상하좌우에 m 만큼의 길이가 더 필요하다.
⚠️ 헤맨 부분.
사실 풀기 막막하면 답부터 먼저 본다. 근데 2개 정도의 블로그를 보면서 '왜 2*m+n 크기의 정사각형을 만들었지?'라는 생각을 했다.
처음엔 이해하기 어려워서 그냥 lock과 key로 풀었는데, 풀다보니 왜 사용했는지 알 것 같다.
👩🏻💻 코드.
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int m, n;
vector<vector<int>> rotation(vector<vector<int>> key){
vector<vector<int>> tmp(m, vector<int>(m));
for(int i=0; i<m; i++){
for(int j=0; j<m; j++){
tmp[i][j]=key[m-1-j][i];
}
}
return tmp;
}
bool is_match(int x, int y, vector<vector<int>> key, vector<vector<int>> board){
bool result=true;
// key를 뒀으니 board의 어느 부분을 막았는지 알기 위해 더한다.
for(int i=x; i<x+m; i++){
for(int j=y; j<y+m; j++){
board[i][j]+=key[i-x][j-y];
}
}
// key가 lock 범위를 벗어나도 되니까 board에서 lock 범위만 본다.
// board 값이 2면 돌기가 만났고, 0이면 빈 곳을 막지 못했다는 뜻이다.
// 무조건 1이 되어야 한다.
for(int i=m; i<m+n; i++){
for(int j=m; j<m+n; j++){
if(board[i][j]!=1) result=false;
}
}
return result;
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
bool answer = false;
m=key.size(), n=lock.size();
vector<vector<int>> board(2*m+n, vector<int>(2*m+n));
for(int i=m; i<m+n; i++){
for(int j=m; j<m+n; j++){
// board에 lock 값 대입
board[i][j]=lock[i-m][j-m];
}
}
// board의 격자판에서 key의 상단왼쪽을 어디에 둘 건지, (i,j)는 시작점을 나타낸다.
for(int i=0; i<n+m; i++){
for(int j=0; j<n+m; j++){
for(int k=1; k<=4; k++){
key=rotation(key);
// 원래 lock, key로만 해서 board 자리에 lock이 있었다.
// board를 사용하고 나서 lock을 board로 안 바꿔줘서 자꾸 seg 떴다.
// 으이그 좀 챙겨!
answer=is_match(i,j,key,board);
if(answer) return answer;
}
}
}
return answer;
}😎 후기.
사실 이런 문제는 알고리즘을 써서 풀어야 한다는 스트레스보단, '아 이걸 언제 다 구현하고 앉아있지...' 라는 느낌 때문에 풀기 막막하다.
개인적으론 눈에 딱 이 알고리즘을 써야 한다는 게 보이는 문제를 좋아하기 때문에, 이런 문제는... 정말이지... 난감한걸...🙈
파닥파닥