문제 요약
열쇠의 돌기(1)를 자물쇠의 홈(0)에 맞춰 자물쇠를 열어야 한다.
열쇠는 90도 단위로 회전하고 모든 위치로 이동할 수 있다. 자물쇠 영역 안에서는 다음 조건을 만족해야 한다.
- 자물쇠의 홈과 열쇠의 돌기가 만나야 한다.
- 자물쇠의 돌기와 열쇠의 돌기가 만나면 안 된다.
- 자물쇠의 모든 칸이 빈 곳 없이 채워져야 한다.
조건을 만족하는 회전과 이동이 하나라도 존재하면 True, 없으면 False를 반환한다.
핵심 아이디어
자물쇠 영역 안에서 각 칸의 합이 정확히 1이면 조건을 만족한다.
| 자물쇠 | 열쇠 | 합 | 결과 |
|---|---|---|---|
| 0 | 0 | 0 | 홈이 채워지지 않음 |
| 0 | 1 | 1 | 정상 |
| 1 | 0 | 1 | 정상 |
| 1 | 1 | 2 | 돌기끼리 충돌 |
따라서 열쇠를 자물쇠에 더한 뒤 자물쇠 영역의 모든 값이 1인지 검사하면 된다.
3N x 3N 확장 보드
열쇠는 자물쇠 밖으로 이동할 수 있다. 자물쇠와 같은 크기의 보드만 사용하면 열쇠의 일부 또는 전부가 바깥에 있는 경우를 처리하기 어렵다.
자물쇠 크기가 N이라면 3N x 3N 크기의 확장 보드를 만들고, 가운데 영역에 자물쇠를 배치한다.
확장 보드
0 ~ N - 1 : 왼쪽·위쪽 여유 공간
N ~ 2N - 1 : 자물쇠 영역
2N ~ 3N - 1 : 오른쪽·아래쪽 여유 공간이 구조에서는 열쇠가 자물쇠 밖으로 완전히 벗어나는 경우와 일부만 겹치는 경우를 모두 인덱스 예외 없이 검사할 수 있다.
열쇠 회전
열쇠는 0도, 90도, 180도, 270도 네 방향만 확인하면 된다.
시계 방향 90도 회전은 다음과 같이 구현할 수 있다.
def rotate(key):
return [list(row) for row in zip(*key[::-1])]key[::-1]로 행 순서를 뒤집고, zip(*...)으로 전치하면 시계 방향 90도 회전 결과가 된다.
풀이 과정
3N x 3N확장 보드를 만든다.- 확장 보드의 중앙
N x N영역에 자물쇠를 복사한다. - 현재 열쇠 방향에서 가능한 모든 시작 위치를 확인한다.
- 열쇠를 확장 보드에 더한다.
- 중앙 자물쇠 영역의 모든 값이
1인지 확인한다. - 성공하면 즉시
True를 반환한다. - 실패하면 열쇠 값을 다시 빼서 원상 복구한다.
- 열쇠를 90도 회전한 뒤 총 네 방향을 검사한다.
Python 코드
def solution(key, lock):
def rotate(matrix):
return [list(row) for row in zip(*matrix[::-1])]
def is_unlocked(board):
for row in range(n, 2 * n):
for col in range(n, 2 * n):
if board[row][col] != 1:
return False
return True
n = len(lock)
m = len(key)
# 열쇠가 자물쇠 바깥에 있는 경우까지 처리하기 위한 확장 보드
board = [[0] * (3 * n) for _ in range(3 * n)]
# 확장 보드의 중앙에 자물쇠 배치
for row in range(n):
for col in range(n):
board[row + n][col + n] = lock[row][col]
for _ in range(4):
# key의 시작 위치를 (0, 0)부터 (2N - 1, 2N - 1)까지 이동한다.
for start_row in range(2 * n):
for start_col in range(2 * n):
# 열쇠를 보드에 더한다.
for row in range(m):
for col in range(m):
board[start_row + row][start_col + col] += key[row][col]
if is_unlocked(board):
return True
# 다음 위치를 검사할 수 있도록 열쇠를 다시 뺀다.
for row in range(m):
for col in range(m):
board[start_row + row][start_col + col] -= key[row][col]
key = rotate(key)
return False코드 설명
자물쇠 중앙 배치
board[row + n][col + n] = lock[row][col]자물쇠를 확장 보드의 중앙에 배치한다. 이후 자물쇠의 실제 영역은 행과 열 모두 n부터 2 * n - 1까지다.
열쇠 추가와 원상 복구
board[start_row + row][start_col + col] += key[row][col]현재 위치에서 열쇠와 자물쇠를 겹친 결과를 만들기 위해 열쇠 값을 더한다.
검사가 끝난 뒤에는 같은 위치에서 열쇠 값을 다시 빼야 다음 이동 위치를 독립적으로 검사할 수 있다.
board[start_row + row][start_col + col] -= key[row][col]자물쇠 열림 확인
if board[row][col] != 1:
return False중앙 자물쇠 영역의 값이 0이면 홈이 채워지지 않은 상태다.
값이 2이면 열쇠 돌기와 자물쇠 돌기가 겹친 상태다.
모든 값이 1일 때만 자물쇠가 열린다.
정확성
알고리즘은 열쇠의 네 가지 회전 상태를 모두 검사한다.
각 회전 상태에서 확장 보드의 모든 가능한 시작 위치에 열쇠를 배치한다. 확장 보드의 중앙에는 자물쇠가 있고, 바깥 영역은 0이므로 열쇠의 자물쇠 밖 부분은 검사 결과에 영향을 주지 않는다.
어떤 배치에서 자물쇠 영역의 모든 값이 1이면, 모든 자물쇠 홈은 열쇠 돌기로 채워지고 돌기끼리 충돌하지 않는다. 따라서 해당 배치로 자물쇠를 열 수 있다.
반대로 자물쇠를 열 수 있는 회전과 이동이 존재한다면, 해당 배치는 알고리즘이 검사하는 네 회전과 시작 위치 중 하나에 포함된다. 이때 자물쇠 영역은 모두 1이므로 알고리즘은 True를 반환한다.
따라서 알고리즘은 자물쇠를 열 수 있을 때만, 그리고 열 수 있다면 반드시 True를 반환한다.
시간 복잡도
자물쇠 크기를 N, 열쇠 크기를 M이라고 하자.
- 회전: 4번
- 열쇠 시작 위치: 최대
(2N)^2 - 열쇠 추가와 복구:
O(M^2) - 자물쇠 검사:
O(N^2)
전체 시간 복잡도는 다음과 같다.
O(4 × (2N)^2 × (M^2 + N^2))N, M이 최대 20이므로 충분히 처리할 수 있다.
공간 복잡도
확장 보드의 크기는 3N x 3N이므로 공간 복잡도는 다음과 같다.
O(N^2)주의할 점
- 열쇠는 네 방향 모두 검사해야 한다.
- 열쇠가 자물쇠 영역 밖으로 나갈 수 있으므로 확장 보드가 필요하다.
- 열쇠를 더한 뒤 반드시 다시 빼서 보드를 원상 복구해야 한다.
- 자물쇠가 처음부터 모든 돌기라면 열쇠를 자물쇠 밖에 배치하는 경우도 가능하므로 바깥 이동을 고려해야 한다.
- 자물쇠 영역은 값이 모두
1이어야 하며,0이나2가 하나라도 있으면 실패다.
정리
이 문제는 회전 4가지와 모든 이동 위치를 확인하는 완전 탐색 문제다.
자물쇠를 확장 보드 중앙에 배치하고, 열쇠를 더한 뒤 중앙 영역이 모두 1인지 검사하면 충돌과 홈 미완성 조건을 간단하게 처리할 수 있다.
