[프로그래머스] 자물쇠와 열쇠

고고학자인 **"튜브"**는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 **1 x 1**인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

제한사항

• key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
• lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
• M은 항상 N 이하입니다.
• key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
  • 0은 홈 부분, 1은 돌기 부분을 나타냅니다.

---

입출력 예

key	lock	result
[[0, 0, 0], [1, 0, 0], [0, 1, 1]]	[[1, 1, 1], [1, 1, 0], [1, 0, 1]]	true

입출력 예에 대한 설명

!https://grepp-programmers.s3.amazonaws.com/files/production/469703690b/79f2f473-5d13-47b9-96e0-a10e17b7d49a.jpg

key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다.

내 코드

회전 부분을 구현하지 못했다.

def solution(key, lock):
    N = len(lock)  # 자물쇠 한 변
    M = len(key)  # 열쇠 한 변
    # key_new = [[0] * N for _ in range(N)]

    # 이동 거리
    for dy in range(-M + 1, N):
        for dx in range(-M + 1, N):
            key_new = [[0] * N for _ in range(N)]  # 기본 세팅

            # 열쇠 좌표 이동
            for y in range(M):
                for x in range(M):
                    nx, ny = x + dx, y + dy

                    # index가 lock 범위 밖이면 넘어감
                    if not (0 <= nx < N and 0 <= ny < N):
                        continue

                    # index가 범위 안이고 1이면 키에 추가
                    elif key[y][x] == 1:
                        key_new[ny][nx] = key[y][x]

            total = sum(sum(row) for row in key_new)

            # 전체가 0이면 넘어감
            if total == 0:
                continue

            # 생성된 key 90도씩 회전하며 lock 위에 대봄
            next_key = False

            for y in range(N):
                for x in range(N):
                    if key_new[y][x] + lock[y][x] != 1:
                        next_key = True
                        break

                if next_key:
                    break

            if next_key:
                continue

            return True  # 통과시 key 맞음

    return False  # 다 돌아도 없으면 key 안맞음

print(solution([[0, 0, 0], [1, 0, 0], [0, 1, 1]], [[1, 1, 1], [1, 1, 0], [1, 0, 1]]))
# print(solution([[1, 0], [0, 0]], [[1, 1, 1], [1, 1, 0], [1, 0, 1]]))

chatGPT

오류 원인 및 수정 사항

1. 자물쇠의 모든 홈(0)이 채워졌는지 정확히 확인해야 함
   • can_unlock() 함수에서 lock의 모든 0이 채워졌는지 체크하는 로직이 불완전했음.
2. 열쇠가 lock과 겹쳐서 1 + 1 = 2가 되는 경우도 확인 필요
   • lock[y]== 1 인 곳에 key의 돌기(1)가 겹치면 안 됨.
3. key를 lock보다 큰 공간에서 움직일 수 있도록 확장된 배열을 사용해야 함
   • lock을 3배 크기의 새로운 배열에 중앙에 배치하여 열쇠 이동을 고려.

---

정답 코드

def rotate_90(matrix):
    """ 시계 방향으로 90도 회전 """
    return [list(row) for row in zip(*matrix[::-1])]

def check(new_lock, N):
    """ 자물쇠의 중앙 부분이 모두 1인지 확인 """
    for y in range(N):
        for x in range(N):
            if new_lock[y + N][x + N] != 1:
                return False
    return True

def solution(key, lock):
    N = len(lock)  # 자물쇠 크기
    M = len(key)   # 열쇠 크기

    # 3배 크기의 새로운 배열 생성 (확장된 자물쇠)
    expanded_size = N * 3
    new_lock = [[0] * expanded_size for _ in range(expanded_size)]

    # 새로운 자물쇠 중앙에 원래 자물쇠 배치
    for y in range(N):
        for x in range(N):
            new_lock[y + N][x + N] = lock[y][x]

    # 열쇠를 4번 회전하며 모든 위치에 시도
    for _ in range(4):
        key = rotate_90(key)

        for dy in range(N * 2):  # 이동 가능한 범위: 확장된 공간 안에서 이동
            for dx in range(N * 2):
                # 열쇠 추가
                for y in range(M):
                    for x in range(M):
                        new_lock[y + dy][x + dx] += key[y][x]

                # 확인
                if check(new_lock, N):
                    return True

                # 열쇠 제거 (원래 상태 복구)
                for y in range(M):
                    for x in range(M):
                        new_lock[y + dy][x + dx] -= key[y][x]

    return False

---

개선된 점

✅ 자물쇠를 3배 확장해서 열쇠 이동을 쉽게 구현

✅ 중앙 부분만 확인하는 check() 함수 추가

✅ 4번 회전하며 모든 위치 탐색 후 원상 복구하여 재사용

✅ 시간 복잡도 최적화 → O(4 * (N+M-1)^2 * N^2) (최대 640,000번 연산)

부가 질문

열쇠 회전 코드를 자세히 설명해줘

🔄 열쇠 회전 코드 설명

def rotate_90(matrix):
    """ 시계 방향으로 90도 회전 """
    return [list(row) for row in zip(*matrix[::-1])]

이 함수는 M x M 크기의 2차원 배열(행렬)을 시계 방향으로 90도 회전시키는 역할을 합니다.

---

💡 핵심 개념: zip()과 리스트 슬라이싱

Python에서 2D 리스트(행렬)를 90도 회 대표적인 방법 중 하나는 zip()을 활용하는 것입니다.

1. matrix[::-1]
   • 원래 행렬을 아래에서 위로(상하 반전) 뒤집습니다.
   • 즉, 마지막 행이 첫 번째 행으로 오고, 첫 번째 행이 마지막 행으로 갑니다.
2. zip(*matrix[::-1])
   • 행렬을 전치(transpose, 행과 열을 교환) 합니다.
   • zip(*iterable)은 여러 리스트를 각각 같은 인덱스끼리 묶어주는 역할을 합니다.
3. [list(row) for row in ...]
   • zip()의 결과는 튜플의 리스트 형태이므로, 다시 리스트로 변환해 2D 리스트 형태로 만듭니다.

---

📌 예제 분석

🔹 원래 행렬 (3x3 크기 예시)

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

🔹 1단계: matrix[::-1] (행 순서 뒤집기)

[
    [0, 1, 1],  # (기존 3번째 행 → 첫 번째 행)
    [1, 0, 0],  # (기존 2번째 행 → 두 번째 행)
    [0, 0, 0]   # (기존 1번째 행 → 세 번째 행)
]

🔹 2단계: zip(*matrix[::-1]) (행과 열 변환)

• zip()을 사용하면 세로로 묶인 값들이 새로운 행이 됨

[
    (0, 1, 0),  # 기존 열(세로)이 새로운 행이 됨
    (1, 0, 0),
    (1, 0, 0)
]

🔹 3단계: list(row) for row in ... (튜플 → 리스트 변환)

[
    [0, 1, 0],
    [1, 0, 0],
    [1, 0, 0]
]

✔ 완성된 회전된 행렬 🎉

key를 시계 방향으로 90도 회전한 결과입니다.

---

💡 zip() 없이 행렬 회전하는 다른 방법

zip()을 사용하지 않고, 직접 행과 열을 변환할 수도 있습니다:

def rotate_90_alt(matrix):
    """ 시계 방향 90도 회전 (인덱스 직접 접근) """
    N = len(matrix)
    rotated = [[0] * N for _ in range(N)]

    for y in range(N):
        for x in range(N):
            rotated[x][N - 1 - y] = matrix[y][x]  # 새로운 위치로 이동

    return rotated

✅ 결과는 동일하지만, zip()을 활용한 방식이 더 간결하고 빠릅니다.

---

🚀 최종 정리

• [::-1]로 행을 뒤집음 (위아래 순서 변경)
• zip(*matrix)로 행과 열을 교환 (전치 행렬)
• list()로 튜플을 리스트로 변환
• 결과적으로 시계 방향 90도 회전 완료 ✅

📌 이 방식은 2D 리스트를 회전하는 대표적인 방법 중 하나이며, 코딩 테스트에서도 자주 활용됩니다! 🚀

내 생각

1. 회전 하는 것 알아놔야겠다.
2. 자물쇠 크기 3배 배열 공간 낭비라고 생각했었는데 크기가 작아서 사용해도 될거 같다.