문제
고고학자인 튜브는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.
잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.
자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.
열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.
풀이과정
원래 1차 풀이는 lock의 모든 0을 포함하는 가장 큰 사각형을 찾은 뒤, 그 사각형만큼으로 자물쇠를 분해하여 각 분해된 미니 자물쇠를 회전했을 때 lock의 모든 0을 포함하는 가장 큰 사각형의 반대 (0은 1로, 1은 0으로)와 일치한다면 True를 리턴하도록 풀었다. 하지만 테스트 케이스만 맞고 실제 실행했을 때는 거의 반절 이상 실패했다. 이유를 생각해보니 자물쇠의 분해가 아닌, 자물쇠 자체를 돌려야한다는 것을 깨달았다. (멍충)
다시 해결해보고, 2차 소스코드를 업데이트해야겠다. 😥
업데이트
소스코드 1차 (42점)
소요 시간 01:10:28
'''
scenario
0. lock에 0이 포함되어있지 않으면 key가 모두 0인 경우에만 가능하다 -> 체크 후 리턴
1. lock에서 0을 포함하는 가장 큰 사각형의 가로, 세로를 찾는다.
2. key의 가로가 1에서 찾은 사각형의 가로, 세로보다 짧으면 False를 리턴
3. key를 1의 가로, 세로 크기로 분할하여 divide 배열에 넣는다.
4. divide 배열을 회전시키며, 1의 사각형과 같아지는 경우가 존재한다면 바로 True를 리턴, 존재하지 않으면 False를 리턴
'''
# 입력된 val이 list안에 없으면 True, 있으면 False
def checkAll(li, val):
for i in range(len(li)):
if val in li[i]:
return False
return True
def makeBigSquare(lock):
answer = [] #사각형의 모습
x, y = [],[]
n = len(lock)
for i in range(n):
for j in range(n):
if lock[i][j] == 0:
x.append(i)
y.append(j)
for i in range(len(lock[min(x): max(x)+1])):
answer.append(list(lock[min(x):max(x)+1][i][j] for j in range(min(y), max(y)+1)))
return answer
def divide(key, i, j, size):
# 각 포인트별로 size만큼씩 순환하여 나눈 배열을 리턴한다.
if i + size > len(key) or j + size > len(key):
return []
answer = []
for x in range(i, i+size):
answer.append([key[x][y] for y in range(j, j+size)])
return answer
def rotate(r):
# 회전 구현
answer = []
for j in range(len(r[0]) - 1, -1, -1):
answer.append([r[i][j] for i in range(len(r))])
return answer
def solution(key, lock):
if checkAll(lock, 0):
return True
m = len(key)
square = makeBigSquare(lock)
for i in range(len(square)):
for j in range(len(square[0])):
if square[i][j] == 0:
square[i][j] = 1
else:
square[i][j] = 0
if len(square) > m: #분할한 사각형의 크기가 key의 크기보다 큰 경우
return False
div = list()
for i in range(m):
for j in range(m):
tmp = divide(key, i, j, len(square))
if tmp != []:
div.append(tmp)
for i in range(len(div)):
r = div[i]
for _ in range(3):
if r == square:
return True
r = rotate(r)
return False소스코드 2차
def check(start_x, start_y, key, lock, wide_size, start, end):
wide_list = [[0] * wide_size for _ in range(wide_size)]
# wide_list에 key 추가, 시작점에서 위아래만큼 key룰 추가하는 것임.
for i in range(len(key)):
for j in range(len(key)):
wide_list[start_x+i][start_y+j] += key[i][j]
# wide_list에 lock을 추가하며 기존 값과 더한다.
for i in range(start, end):
for j in range(start, end):
wide_list[i][j] += lock[i - start][j- start]
if wide_list[i][j] != 1:
return False
return True
def solution(key, lock):
m, n = len(key), len(lock)
start = m - 1 #start point of lock in wide_list
end = start + n # end point of lock in wide_list
wide_size = n + start * 2 #size of wide_list
# To move a key over a fixed lock position
for i in range(0, 4): # origin, 90, 180, 270
for j in range(end):
for k in range(end):
if check(j, k, key, lock, wide_size, start, end):
return True
key = list(zip(*key[::-1])) #rotate
return False