자물쇠와 열쇠
문제
고고학자인 튜브는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.
잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.
자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.
열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.
제한사항
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은 돌기 부분을 나타냅니다.
예시
# key, lock, result
[[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true
풀이
열쇠를 4방향으로 회전할 수 있고 좌우로 움직일 수 있다. 열쇠는 자물쇠 영역 밖으로 나갈 수 있으므로 단 한칸만 걸치는 끝 모서리부터 옮겨가며 검사하면 된다.
자물쇠의 튀어나와 있는 부분이 1이고 열쇠의 홈이 0이므로, 자물쇠와 열쇠를 현재 위치에 맞춰 더했을 때 자물쇠의 모든 영역이 1이면 자물쇠가 딱 맞는다는 뜻이다. 아래 풀이에서 자물쇠가 한칸만 걸칠때를 기준으로 자물쇠를 넘어가는 부분까지 새로운 배열을 만들었다. 그리고 그 부분을 모두 3으로 채웠다. 이렇게 하면 마지막에 검사할 때, 전체 배열에서 2가 없고 0이 없으면 자물쇠가 맞는다는 뜻이 된다. (2는 자물쇠의 돌기와 열쇠의 돌기가 만났을 때만 나오는 수이고, 0이 없다는 것은 빈칸이 없다는 뜻이기 때문이다.) 이렇게 확인해주면서 오른쪽과 아래방향으로 이동하면 되고, 열쇠를 4방향 돌려서 각각 실행해보면 된다.
import copy
def isCorrect(m):
for y in range(len(m)):
for x in range(len(m)):
if m[y][x] == 2 or m[y][x] == 0:
return False
return True
def rotate(m):
new_key = [[0] * len(m) for _ in range(len(m))]
# 회전전 (y, x) 회전 후 (x, 길이-y-1)
for y in range(len(m)):
for x in range(len(m)):
new_key[x][len(m)-y-1] = m[y][x]
return new_key
def solution(key, lock):
# 회전 4번, 오른쪽 M, 왼쪽 M, 위 M, 아래 M 경우의 수 (이동은 M x M의 영역에 조금이라도 걸치면 계속 진행)
# lock에서 자물쇠크기-1 만큼 상하좌우로 크기를 늘려야한다. 자물쇠의 위치는 m-1부터 m-1+n-1
m = len(key[0])
n = len(lock[0])
# 확장된 lock 만들기
big_lock = []
for y in range(0, n+(m*2)-2):
tmp_x = []
for x in range(0, n+(m*2)-2):
if y>=m-1 and y<=m-1+n-1 and x>=m-1 and x<=m-1+n-1:
tmp_x.append(lock[y-m+1][x-m+1])
else: tmp_x.append(3)
big_lock.append(tmp_x)
for _ in range(4):
key = rotate(key)
# key 넣어보기, 복잡도 20x20x20x20
for y in range(0, len(big_lock)-m+1):
for x in range(0, len(big_lock)-m+1):
# 초기화
tmp_big_lock = copy.deepcopy(big_lock)
for dy in range(0, m):
for dx in range(0, m):
tmp_big_lock[y+dy][x+dx] += key[dy][dx]
# for i in tmp_big_lock:
# for j in i:
# print(j, end='')
# print("")
# print('---------------')
# 맞춰졌는지 확인 (big_lock에서 2가 없고 0이 없을 때)
if isCorrect(tmp_big_lock): answer = True; return answer
answer = False
return answer