문제 간단 해석
정사각형 형태의 자물쇠와 열쇠가 있고, 열쇠의 크기는 자물쇠보다 작거나 같다.
자물쇠의 홈(빈 공간, 0)을 열쇠의 돌기(튀어나온 부분, 1)로 모두 채우면 자물쇠가 열리는데, 현실에서도 그렇듯 자물쇠의 돌기와 열쇠의 돌기가 서로 맞닿으면 열쇠를 밀어넣을 수조차 없다.
즉, 자물쇠의 0은 모두 열쇠의 1과 맞닿아야만 하고, 자물쇠의 1과 열쇠의 1이 만나는 순간 해당 방법은 폐기해야 한다.
풀이 코드
def solution(key, lock):
N = len(lock)
M = len(key)
zeroPoint = [(r, c) for c in range(N) for r in range(N) if lock[r][c] == 0]
if len(zeroPoint) == 0:
return True
zeroPointMaxMin = [(min(x), max(x)) for x in zip(*zeroPoint)]
endPoint, zeroPointMax = zip(*zeroPointMaxMin)
startPoint = (zeroPointMax[0] - M + 1, zeroPointMax[1] - M + 1)
startY, startX = startPoint
endY, endX = endPoint
def check(y, x):
for dy in range(M):
for dx in range(M):
if 0 <= y + dy < N and 0 <= x + dx < N and lock[y + dy][x + dx] ^ key[dy][dx] == 0:
return False
return True
for _ in range(4):
for r in range(endY - startY + 1):
for c in range(endX - startX + 1):
if check(startY + r, startX + c):
return True
key = [list(reversed(x)) for x in zip(*key)]
return False
해석
무작정 열쇠를 돌려가며 자물쇠에 매칭하면 비효율적이라 생각했다. 따라서 자물쇠의 빈 공간을 먼저 탐색한 후, 빈 공간들의 영역에만 열쇠를 가져다 대는 방식을 떠올렸다.
빈 공간 탐색
zeroPoint = [(r, c) for c in range(N) for r in range(N) if lock[r][c] == 0]
if len(zeroPoint) == 0:
return True이중 for문을 돌려 0으로 표현된 홈들을 찾아내고, 하나의 리스트 안에 넣어두었다.
헌데 홈이 없는 자물쇠라면 이미 열리는 녀석일 테니 True를 return해 주었다.
빈 공간들의 영역 구하기
zeroPointMaxMin = [(min(x), max(x)) for x in zip(*zeroPoint)]
endPoint, zeroPointMax = zip(*zeroPointMaxMin)
startPoint = (zeroPointMax[0] - M + 1, zeroPointMax[1] - M + 1)
startY, startX = startPoint
endY, endX = endPoint위에서 구한 zeroPoint는 (y, x)가 나열된 리스트이다.
자물쇠가 위와 같은 형태라고 생각해 보자.
zeroPoint는 [(1, 2), (3, 1), (3, 3), (4, 1)] 형태이다.
이 때, 빈 공간들을 모두 채울 수 있는 사각형의 영역은
해당 영역과 같을 것이다.
즉, 열쇠는 위와 같은 사각형의 영역을 모두 커버할 수 있어야 한다.
만약 그렇지 못 할 경우, 무조건 채울 수 없는 홈이 생겨 자물쇠를 열 수 없기 때문이다.
해당 사각형은 (1, 1), (4, 3)으로 표현(좌측 상단, 우측 하단)할 수 있으며, 이는 zeroPoint 배열에서 (y 최소값, x 최소값), (y 최대값, x 최대값)으로 표현할 수 있다.
따라서 y는 y끼리, x는 x끼리 분리하여 들고 있을 필요가 있다.
y, x 분리 및 최대, 최소값 찾기
zeroPointMaxMin = [(min(x), max(x)) for x in zip(*zeroPoint)]*을 써서 zeroPoint를 분리한다. 리스트를 해제한다고 생각하면 쉽다.
(1, 2), (3, 1), (3, 3), (4, 1)
그 이후 zip으로 각각의 자리값을 묶는다.
(1, 3, 3, 4), (2, 1, 3, 1)
묶은 값들을 min과 max를 이용하여 최솟값, 최대값을 찾는다.
[(1, 4), (1, 3)]
사각형 영역 알아내기
endPoint, zeroPointMax = zip(*zeroPointMaxMin)현재 zeroPointMaxMin은 [(y 최솟값, y 최댓값), (x 최솟값, x 최댓값)]으로 구분되어 있다.
(y, x) 순으로 다시 맞추려면 자리값을 묶어줘야 할 필요가 있으므로 다시 zip을 사용한다.
해당 값은 (1, 1), (4, 3)으로, 사각형 영역을 구할 수 있다.
사각형 영역을 모두 커버하는 열쇠의 영역 구하기
startPoint = (zeroPointMax[0] - M + 1, zeroPointMax[1] - M + 1)
startY, startX = startPoint
endY, endX = endPoint위의 부분에서 사각형 영역의 맨 좌측 끝을 endPoint라고 이름지었다. 왜일까?
기준 잡기 나름이지만, M=5인 열쇠가 있다고 가정하자.
해당 열쇠가 영역을 모두 커버하려면, 열쇠의 좌상단, 우하단이 영역의 좌상단, 우하단과 일치하여야 한다.
우하단이 일치
좌상단이 일치
이 때 열쇠의 좌상단을 기준으로, 열쇠의 존재 가능한 영역은 사각형 영역과 우하단이 일치하는 상태의 시점부터 사각형 영역의 좌상단까지이다.
즉 사각형 영역의 우하단에서 y축과 x축을 M - 1만큼 옮기면, 열쇠가 존재 가능한 영역을 구할 수 있다.
영역의 좌상단은 알고 있으니 endPoint로 두고, 우하단에서 M - 1만큼 빼주면 완료.
보기 이쁘게 startPoint와 endPoint를 Y, X로 나눠주자.
영역에 맞게 열쇠 매칭하기
for _ in range(4):
for r in range(endY - startY + 1):
for c in range(endX - startX + 1):
if check(startY + r, startX + c):
return True
key = [list(reversed(x)) for x in zip(*key)]
return False
열쇠를 영역에 맞게끔 반복시키며 매칭해보자. 매칭하는 함수는 밑에서 확인할 텐데, 완벽하게 매칭된다면 True, 아니라면 False를 반환하게끔 해 줄 것이다.
따라서 열쇠를 옮겨가며 매칭해보되, 반환값이 True라면 그대로 True를 반환하고 False라면 이어서 매칭을 시도할 것이다.
열쇠를 반복적으로 옮겨가며 매칭하기
for r in range(endY - startY + 1):
for c in range(endX - startX + 1):
if check(startY + r, startX + c):
return True열쇠의 자리를 옮기며 매칭해야 하는데, 해당 자리는 startPoint에서 endPoint까지이다. range(startY, endY + 1)로 지정하고 check함수에 그대로 변수를 넣는 게 더 가독성이 좋을 것 같다.
만약 열쇠가 해당 영역을 채울 수 없는 크기라면, for문이 돌지 않고 알아서 False를 내뱉게 된다. endPoint보다 startPoint가 더 커지기 때문이다.
열쇠 회전시키기
for _ in range(4):
...
# 열쇠를 반복적으로 옮겨가며 매칭하기
...
key = [list(reversed(x)) for x in zip(*key)]
만약 영역을 옮겨 가며 매칭했는데도 열리지 않는다면, 열쇠를 90도 회전시켜서 진행해봐야 할 필요가 있다.
귀찮으니까 M = 3인 열쇠로 규칙을 찾아보자.
해당 열쇠를 시계방향으로 90도 돌린다면,
그림과 같은 배열로 재탄생해야 한다.
규칙을 자세히 관찰하자면, 회전시키기 전의 맨 앞열(1, 4, 7)이 회전시킨 후의 맨 위 행(7, 4, 1)으로 변한다.
그러므로 zip을 사용하여 열끼리 모아 행을 만들건데, 그대로 만들면 순서가 맞지 않으니 reversed를 사용하여 순서를 맞춰준다.
(물론 key 자체를 reversed한 후 zip해줘도 무방하다. 그게 더 빠를지도..?)
매칭 함수
def check(y, x):
for dy in range(M):
for dx in range(M):
if 0 <= y + dy < N and 0 <= x + dx < N and lock[y + dy][x + dx] ^ key[dy][dx] == 0:
return False
return True우리는 y, x로 현재 열쇠의 시작점 좌표를 건네받았다.
열쇠는 M * M이므로 해당 열쇠의 홈, 돌기와 자물쇠의 홈, 돌기가 제대로 맞는지 검사해야 한다.
dy, dx로 열쇠의 칸을 판별한다. 이 때 자물쇠는 y, x부터 차례로 검사해야 하지만, 열쇠의 한 칸이 자물쇠의 범위를 벗어났을 경우에는 아무런 영향을 끼치지 못 하기 때문에 0 <= y + dy < N 식으로 범위를 검사해준다.
열쇠의 한 칸이 자물쇠 범위에 들어왔고, 두 값이 서로 다른 경우를 확인해야 한다.
만약 둘 다 홈이거나 돌기라면, 자물쇠는 열리지 않을 것임을 우리는 안다.
그러므로 XOR를 이용하여 두 값이 서로 다른지를 판단하자.
만약 홈과 돌기가 꼭 맞는 경우(lock과 key의 내부값이 모두 다 다른 경우)를 구했다면 자연스레 True를 반환하여 자물쇠가 열렸음을 알려주자.
