1. 요약
키와 자물쇠가 주어졌다. 자물쇠를 풀어야하는데, 키를 이동시키거나 회전시켜서 키의 돌기와 자물쇠의 홈이 맞으면 자물쇠가 풀린다. 자물쇠와 키는 홈과 돌기로 구성된다. 주의해야할 점은 키의 돌기와 자물쇠의 돌기가 만나면 안된다. 자물쇠가 풀리는지 풀리지 않는지 확인하는 문제다.
2. 아이디어
문제에 따르면, 자물쇠의 일부영역과 키의 일부영역을 겹쳐서 자물쇠의 성분과 키의 성분을 비교할 수 있다고한다. 따라서, 자물쇠를 확장해야한다. 확장하는 방법은 자물쇠의 위, 아래, 오른쪽, 왼쪽에 -1를 (키의길이-1)x2 만큼 추가한다.
이후, 키와 자물쇠의 비교를 위해 자물쇠의 시작점을 둔다. 코드에서는 비교 연산을 하는 시작점이 좌측 상단이다. 비교 연산이 종료된 후, 자물쇠가 풀리지 않았으면 키를 우측으로 90도 회전하고 다시 비교연산을 수행한다. 만약 360도를 회전했는데도, 자물쇠가 풀리지 않았으면 거짓을 반환한다. 반대로, 360도 회전을 하기전에 자물쇠가 풀렸으면 참을 반환한다.
3. 코드
from collections import deque
key_len = 0
lock_len = 0
zeros = 0
def rotate(key):
q = deque()
n = len(key)
for col in range(n):
for row in range(n-1, -1, -1):
q.append(key[row][col])
for i in range(n):
for j in range(n):
key[i][j] = q.popleft()
return key
def isin(y, x):
global key_len, lock_len
if y + key_len -1 < lock_len and x + key_len -1 < lock_len: return True
return False
def operations(y, x, key, lock):
global key_len, zeros
_zeros = zeros
y_key = 0
for i in range(y, y+key_len):
x_key = 0
for j in range(x, x+key_len):
if key[y_key][x_key] == 1 and lock[i][j] == 1: return False
elif key[y_key][x_key] == 1 and lock[i][j] == 0: _zeros -= 1
x_key += 1
y_key += 1
return _zeros == 0
def solve(k, key, lock):
global key_len, lock_len, zeros
if k > 0: key = rotate(key)
if k == 4:
return False
for i in range(lock_len):
for j in range(lock_len):
if isin(i, j) and operations(i, j, key, lock): return True
ok = solve(k+1, key, lock)
return ok
def solution(key, lock):
global zeros, key_len, lock_len
for lock_col in lock:
zeros += lock_col.count(0)
answer = True
key_len = len(key)
lock_len = len(lock)
t = 2*(key_len-1) + lock_len
tmp = [[-1 for _ in range(t)]]
padding = [-1 for _ in range(key_len-1)]
for i in range(lock_len):
lock[i] = padding + lock[i] + padding
lock = tmp * (key_len-1) + lock + tmp * (key_len-1)
lock_len = t
answer = solve(0, key, lock)
return answer