문제
- 문제 링크
- 문제 설명: MxM 2차원 배열인 열쇠를 회전/이동 하여 NxN 2차원 배열인 자물쇠의 모든 홈 부분과 열쇠의 돌기가 딱 맞게 매칭 시킬 수 있으면 true, 아니면 false를 반환하는 함수 작성.
- 자물쇠의 돌기와 열쇠의 돌기가 마주치면 안됌.
- 열쇠의 범위가 자물쇠 범위 밖에 있을 경우 영향을 주지 않음.
- 입력
- key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열
- lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열
- M은 항상 N 이하
- key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
- 0은 홈 부분, 1은 돌기 부분을 나타냅니다.
- 출력: 매칭이 되면 true, 아니면 false
| key | lock | result |
| [[0, 0, 0], [1, 0, 0], [0, 1, 1]] |
[[1, 1, 1], [1, 1, 0], [1, 0, 1]] |
true |
풀이
- 2차원 배열의 크기가 크지 않기 때문에 naive하게 열쇠를 돌리는 함수(rotate)와 1칸씩 움직이면서 열쇠와 자물쇠가 겹치는 부분에 대해 모든 원소가 매칭이 되는지 검사하는 함수(canLock)를 호출
- 말은 쉬운데 구현하는데 시간이 오래 걸렸던 문제
- rotate 함수를 작성할 때 열쇠의 배열 크기 M이 홀수이면 맨 중앙에 있는 값은 그대로 복사해주어야 함
- canLock 함수를 최대한 간단하게 구현하기 위해 각 열쇠와 자물쇠가 겹치는 위치의 좌표만 받음.
- canLock(pii& ks, pii& ls, int yGap, int xGap) := 열쇠의 좌측상단 좌표 ks, 자물쇠의 좌측상단 좌표 ls, 그리고 y축 오프셋과 x축 오프셋.
- 움직일 때는 열쇠의 맨 끝 원소[(N-1,N-1) 좌표]와 자물쇠의 첫번째 원소[(0,0) 좌표]를 맞물리는 것을 시작으로 x축으로 끝까지 이동하고 다 이동하면 y축으로 한 칸씩 늘리면서 진행 M 은 항상 N 이하이기 때문에 M이 N에 포함될 때 열쇠의 겹치는 구간은 변함이 없지만 자물쇠의 구간은 계속 바꾸어 주어야 하는데 주의
- 이런 문제는 단정문(assertion)이 불가피하다.
- 움직이면서 canLock 이 1번이라도 true이면 true를 반환하도록 구현함
#include <string>
#include <vector>
#include <cassert>
#define Y first
#define X second
using namespace std;
typedef pair<int,int> pii;
// 자물쇠를 시계 방향으로 90도 회전하는 함수
void rotate(vector<vector<int>>& old_key) {
int n = old_key.size(), i = 0;
vector<vector<int>> new_key(n, vector<int> (n, 0));
for (; i < n >> 1; i++) { // 가장자리에서부터 회전할 때 최대 깊이는 길이의 절반
for (int j = i; j < n-i; j++) {
// top (i,i)~(i,n-i-1) -> right-side (i,n-i-1)~(n-i-1,n-i-1)
new_key[j][n-i-1] = old_key[i][j];
// right-side (i,n-i-1)~(n-i-1,n-i-1) -> bottom (n-i-1,n-i-1)~(n-i-1,i)
new_key[n-i-1][n-j-1] = old_key[j][n-i-1];
// bottom (n-i-1,i)~(n-i-1,n-i-1) -> left-side (i,i)~(n-i-1,i)
new_key[j][i] = old_key[n-i-1][j];
// left-side (i,i)~(n-i-1,i) -> top (i,n-i-1)~(i,i)
new_key[i][n-j-1] = old_key[j][i];
}
}
if (n & 1) new_key[i][i] = old_key[i][i]; // 길이가 홀수이면 맨 중앙값은 그대로 복사
old_key = new_key;
}
int numZerosOfLock;
// 겹치는 구간에 모든 자물쇠의 홈이 문제없이 매칭된다면 true 반환
bool canLock(vector<vector<int>>& key,
vector<vector<int>>& lock,
pii& ks, pii& ls, int yGap, int xGap)
{
int numMatches = 0;
for (int dy = 0; dy <= yGap; dy++) {
for (int dx = 0; dx <= xGap; dx++) {
auto& kVal = key[ks.Y + dy][ks.X + dx];
auto& lVal = lock[ls.Y + dy][ls.X + dx];
if (kVal == lVal) return false;
if (kVal && !lVal) numMatches++;
}
}
return numMatches == numZerosOfLock;
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
int n = lock.size();
int m = key.size();
numZerosOfLock = 0;
for (int y = 0; y < n; y++)
for (int x = 0; x < n; x++)
if (lock[y][x] == 0)
numZerosOfLock++; // 맨 처음에 자물쇠의 홈의 개수 계산
// 매 회전마다 시도
for (int i = 0; i < 4; i++) {
rotate(key);
pii ks, ke, ls, le;
ks.Y = ke.Y = m-1;
ls.Y = le.Y = 0;
while (ke.Y >= 0) {
ls.X = le.X = 0;
ks.X = ke.X = m-1;
while (ke.X >= 0) { // X축으로 1칸씩 이동하면서 겹치는 구간을 검사
if (canLock(key, lock, ks, ls, ke.Y-ks.Y, ke.X-ks.X))
return true;
if (ks.X > 0) ks.X--; // 열쇠는 자물쇠 배열에서 왼->오 이동할 때 x좌표가 0으로 수렴
else ls.X++; // 열쇠가 자물쇠의 끝에 도달하면 열쇠의 구간의 시작 좌표 x값을 늘려줌
if (le.X < n-1) le.X++; // 열쇠가 왼->오 이동할 때 자물쇠 구간의 끝 좌표 x값을 늘려줌
else ke.X--; // 열쇠가 자물쇠의 끝에 도달하면 열쇠의 구간의 끝 좌표 x값을 줄여줌
assert (le.X - ls.X == ke.X - ks.X);
}
if (ks.Y > 0) ks.Y--; // 열쇠가 자물쇠 배열에서 위->아래 이동할 때 y좌표는 0으로 수렴
else ls.Y++; // 열쇠가 자물쇠의 끝에 도달하면 열쇠의 구간의 시작 좌표 y값을 늘려줌
if (le.Y < n-1) le.Y++; // 열쇠가 이동하면 자물쇠 배열의 구간의 끝 좌표 y값을 늘려줌
else ke.Y--; // 열쇠가 자물쇠의 끝에 도달하면 열쇠의 구간의 끝 좌표 y값을 줄여줌
assert (le.Y - ls.Y == ke.Y - ks.Y);
}
}
return false;
}
'Algorithm > Problem Solving' 카테고리의 다른 글
| [Floyd-Warshall] (프로그래머스 Lv 3) 합승 택시 요금 (0) | 2021.04.24 |
|---|---|
| [SlidingWindow] (프로그래머스 Lv 3) 광고 삽입 (0) | 2021.04.24 |
| [DFS] (프로그래머스 Lv 2) 후보키 (0) | 2021.04.24 |
| [BinarySearch, DFS] (프로그래머스 Lv 2) 순위 검색 (0) | 2021.04.24 |
| [DFS, Bit-Operation, Set] (프로그래머스 Lv 2) 메뉴 리뉴얼 (0) | 2021.04.24 |