https://programmers.co.kr/learn/courses/30/lessons/60059
2차원 배열을 다루는게 익숙해야 풀만할 것 같은 문제.
효율성이 없기 때문에 완전탐색으로 풀면 된다.
자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다. 열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.
입출력 예
key lock result [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true
key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다.
솔루션
1) M*2 + N 크기의 보드를 만들고 중앙에 좌물쇠를 배치한다.
2) key를 4번 돌려가며 차례로 이동시킨다
3) 위에서 아래로 열쇠를 이동했을때 중앙의 키가 모두 1이되면 unlock
def rotate90(arr): # 90도 돌리기
def attach(x, y, M, key, board): # 열쇠 넣어보기
def detach(x, y, M, key, board): # 열쇠 빼기
def check(board, M, N): # 모두 1인지 확인
[(0, 1, 0), (1, 0, 0), (1, 0, 0)]
[(1, 1, 0), (0, 0, 1), (0, 0, 0)]
[(0, 0, 1), (0, 0, 1), (0, 1, 0)]
[(0, 0, 0), (1, 0, 0), (0, 1, 1)]
[[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0]]
코드
# 파이썬
def attach(x, y, M, key, board):
for i in range(M):
for j in range(M):
board[x+i][y+j] += key[i][j]
def detach(x, y, M, key, board):
for i in range(M):
for j in range(M):
board[x+i][y+j] -= key[i][j]
def rotate90(arr):
return list(zip(*arr[::-1]))
def check(board, M, N):
for i in range(N):
for j in range(N):
if board[M+i][M+j] != 1:
return False;
return True
def solution(key, lock):
M, N = len(key), len(lock)
board = [[0] * (M*2 + N) for _ in range(M*2 + N)]
# 자물쇠 중앙 배치
for i in range(N):
for j in range(N):
board[M+i][M+j] = lock[i][j]
rotated_key = key
# 모든 방향 (4번 루프)
for _ in range(4):
rotated_key = rotate90(rotated_key)
for x in range(1, M+N):
for y in range(1, M+N):
# 열쇠 넣어보기
attach(x, y, M, rotated_key, board)
# lock 가능 check
if(check(board, M, N)):
return True
# 열쇠 빼기
detach(x, y, M, rotated_key, board)
return False