자물쇠와 열쇠

문제 보기 · Level 3 · 2020 KAKAO BLIND RECRUITMENT · 정답률 42% · 푼 사람 12,359명 (2026-09-30 기준)¹

문제

N×N 자물쇠와 M×M 열쇠가 0(홈)과 1(돌기)로 주어진다. 열쇠를 회전·이동해 자물쇠에 겹친다. 자물쇠 영역 안에서 자물쇠의 홈이 모두 열쇠 돌기로 채워지고 돌기끼리 만나지 않으면 열린다. 자물쇠 밖으로 나간 열쇠 부분은 상관없다. 열 수 있으면 true, 없으면 false를 돌려준다.

3 ≤ M ≤ N ≤ 20

풀이

막히면 한 단계씩 펼친다².

필요한 개념

완전탐색: 회전 4가지 × 놓는 위치 모두를 해 본다.
구현과 시뮬레이션: 격자 90도 회전 zip(*a[::-1]), 두 격자 겹치기.

1단계 · 작은 예로 손으로 풀기

자물쇠 칸마다 “자물쇠 값 + 겹친 열쇠 값”을 더한다(겹친 열쇠가 없으면 0).

홈(0) + 돌기(1) = 1 → 채워졌다
돌기(1) + 홈(0) = 1 → 그대로
돌기(1) + 돌기(1) = 2 → 부딪힘, 안 된다
홈(0) + 홈(0) = 0 → 비었다, 안 된다

그래서 “자물쇠의 모든 칸이 합 1이면 열린다”로 한 줄에 정리된다. 합이 1이라는 것은 둘 중 정확히 하나만 1이라는 뜻이라, 칸마다 자물쇠 XOR 열쇠가 1인 것과 같다(불 대수와 논리 회로).

2단계 · 가장 단순한 방법과 그 속도

회전 4가지마다, 열쇠를 자물쇠와 한 칸이라도 겹치게 놓는 위치는 (N + M − 1)²가지다. N = M = 20이면 39² = 1,521가지다. 위치마다 자물쇠 N² = 400칸을 보면 4 × 1,521 × 400 ≈ 243만 번이다. 된다. 틀린 칸을 만나면 바로 다음 위치로 넘어가니 실제로는 더 적다.

3단계 · 핵심 아이디어

회전: 시계 방향 90도는 [list(r) for r in zip(*key[::-1])]다. zip(*a)는 행과 열을 맞바꾸는 전치라서, 위아래를 먼저 뒤집고([::-1]) 전치하면 시계 방향으로 돈다. 네 번 돌리면 모든 방향을 본다.
위치: 열쇠의 왼쪽 위 칸이 자물쇠 좌표 (dr, dc)에 온다고 하자. dr, dc는 −(M − 1)부터 N − 1까지다(음수면 열쇠 일부가 자물쇠 위·왼쪽 밖에 있다).
확인: 자물쇠 칸 (r, c)에 겹친 열쇠 칸은 (r − dr, c − dc)다. 열쇠 범위 밖이면 0으로 친다. 모든 칸에서 자물쇠 + 열쇠 = 1이면 열린다.
홈이 없는 자물쇠: 채울 홈이 없으니 열쇠를 자물쇠 밖에 두면 된다. 바로 true다.

4단계 · 코드 흐름

자물쇠에 홈이 없으면 true.
네 번 되풀이: 열쇠를 90도 돌린다. 모든 (dr, dc)마다 자물쇠 모든 칸의 합이 1인지 본다. 그런 곳이 있으면 true.
끝까지 없으면 false.

5단계 · 파이썬 코드

def solution(key, lock):
    N, M = len(lock), len(key)
    if all(v == 1 for row in lock for v in row):      # 홈이 없다
        return True

    def fits(k, dr, dc):
        for r in range(N):
            for c in range(N):
                kr, kc = r - dr, c - dc                 # 이 칸에 겹친 열쇠 칸
                kv = k[kr][kc] if 0 <= kr < M and 0 <= kc < M else 0
                if lock[r][c] + kv != 1:
                    return False
        return True

    for _ in range(4):
        key = [list(r) for r in zip(*key[::-1])]      # 시계 방향 90도
        for dr in range(-(M - 1), N):
            for dc in range(-(M - 1), N):
                if fits(key, dr, dc):
                    return True
    return False

all(v == 1 for row in lock for v in row): 두 겹 반복을 한 줄로 쓴 것이다. 모든 칸이 1이면 참이다.
fits는 처음으로 틀린 칸에서 바로 False를 돌려주어 빨리 끝난다.

6단계 · 실행 추적

key = [[0,0,0],[1,0,0],[0,1,1]], lock = [[1,1,1],[1,1,0],[1,0,1]]

자물쇠의 홈은 (1, 2)와 (2, 1) 두 칸이다.
한 번 돌린 열쇠는 [[0,1,0],[1,0,0],[1,0,0]]이다. 돌기는 (0, 1), (1, 0), (2, 0)에 있다.
왼쪽 위를 자물쇠 (1, 1)에 놓으면: 돌기 (0, 1) → 자물쇠 (1, 2) 홈을 채움, (1, 0) → (2, 1) 홈을 채움, (2, 0) → (3, 1)은 자물쇠 밖이라 상관없다.
나머지 칸은 자물쇠 돌기 + 열쇠 홈(또는 열쇠 없음) = 1이다.

열린다 → true

7단계 · 복잡도와 흔한 실수

4 × (N + M − 1)² × N²이라 최악 약 240만 번이다. 판이 아주 크면 위치마다 “자물쇠 돌기 × 열쇠 돌기”의 합(부딪힌 칸 수, 0이어야 한다)과 “자물쇠 홈 × 열쇠 돌기”의 합(채운 홈 수, 홈 개수와 같아야 한다)만 보면 된다. 두 합은 열쇠를 밀며 곱해 더하는 상호상관이라, 합성곱처럼 FFT로 모든 위치를 한꺼번에 구할 수 있다.

열쇠가 자물쇠 안에만 놓인다고 생각해 위치를 0 ~ N − M으로만 본다. 열쇠는 밖으로 삐져나갈 수 있다.
돌기끼리 부딪히는 경우(합 2)를 확인하지 않는다.
회전을 반시계로 하거나 한 방향만 본다. 네 방향을 다 보면 방향은 상관없다.

검증: 문제의 예시를 통과했고, 무작위 입력 1,500개(N·M 3~5)에서 “자물쇠를 가운데 둔 큰 판을 만들고 열쇠 돌기 좌표 집합을 옮겨 가며 겹치는” 다른 풀이와 결과가 같았다. 6단계의 회전과 위치도 계산해 확인했다 — 16_pg60059_p1.py

프로그래머스 스쿨, “자물쇠와 열쇠” (https://school.programmers.co.kr/learn/courses/30/lessons/60059), 2026-09-30 조회. ↩
“홈이 없으면 열쇠를 밖에 두어 true”는 문제 문장(“자물쇠 영역을 벗어난 열쇠 부분은 영향을 주지 않는다”, “모든 홈을 채워야 한다”)을 그대로 읽은 해석이다. 열쇠를 자물쇠와 한 칸 이상 겹치게만 두는 흔한 풀이와 답이 갈리는 경우는 “자물쇠에 홈이 없고 열쇠의 네 모서리가 모두 돌기”일 때뿐이다(3×3 자물쇠에서 3×3 열쇠 512개를 모두 넣어 보면 갈리는 것은 네 모서리가 돌기인 32개뿐이다). 열쇠의 모서리 하나라도 홈이면 그 모서리 한 칸만 겹쳐 두는 것으로 두 풀이 모두 true가 된다. 문제 문장의 조건(겹친 곳에서 돌기끼리 만나지 않음, 모든 홈이 참)은 열쇠를 밖에 둘 때 모두 만족되므로 이 풀이는 문장대로 true를 낸다. ↩