[프로그래머스 / Python파이썬] 자물쇠와 열쇠

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠

 

 

문제 설명

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

 

잠겨있는 자물쇠는 격자 한 칸의 크기가 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

 

 

 

문제 풀이

문제에서 요구하는 바를 정확하게 구현하면 되는 문제였다. key와 lock의 최대 크기가 20이므로 각 원소를 모두 탐색한다 해도 20 x 20 = 400번이다. 따라서 완전 탐색으로 문제를 해결할 수 있다. 

 

처음에 열쇠를 (0, 0)부터 (N, N)까지만 이동시키면 된다고 잘못 생각해서 꼬였었다. 열쇠의 마지막 부분 (M, M)으로 자물쇠의 시작 부분 (0, 0)을 여는 경우까지 생각을 못했던 것이다. 스튜핏~~

이를 편하게 처리하기 위해 자물쇠를 원래 크기의 3배를 하고 원본을 가운데에 두었다. 예를 들어 원래의 lock 다음과 같은 3 x 3 배열이라고 하면

아래와 같이 9 x 9 배열로 바꿀 수 있다. 

 

자물쇠를 여는 조건은 다음과 같다. 

1. lock이 0이면 key가 1이어야 한다. 
2. lock이 1이면 key가 0이어야 한다. 

따라서 lock과 key를 더했을 때 lock의 모든 원소가 1이면 자물쇠를 열 수 있다. 따라서 조건에 맞게 key를 이동 및 회전해가며 자물쇠를 열 수 있는지 탐색하면 된다. 

 

완전 탐색을 잘 구현했다고 생각했는데 자꾸 테스트 케이스 4개 정도를 틀려서 헤맸다. 알고 보니 2차원 리스트 회전을 구현하는 부분에서 result[n - r - 1][n - c - 1]을 result[n - c - 1][n - r - 1]로 잘못 쓰는 실수가 있었다.😭 구현 문제를 풀 때 이런 사소한 실수를 하는 경우가 종종 있었다. 앞으로 코드 짤 때 더 꼼꼼히 살펴보고 실수를 줄여야겠다..!

 

 

 

소스코드

# 자물쇠와 열쇠

# NxN 2차원 리스트 d도 회전
# 회전 각도 d => 1: 90도, 2: 180도, 3: 270도
def rotate(array, d):
    n = len(array)  # 배열의 길이
    result = [[0] * n for _ in range(n)]

    if d % 4 == 1:
        for r in range(n):
            for c in range(n):
                result[c][n - r - 1] = array[r][c]
    elif d % 4 == 2:
        for r in range(n):
            for c in range(n):
                result[n - r - 1][n - c - 1] = array[r][c]
    elif d % 4 == 3:
        for r in range(n):
            for c in range(n):
                result[n - c - 1][r] = array[r][c]
    else:
        for r in range(n):
            for c in range(n):
                result[r][c] = array[r][c]

    return result


# 자물쇠 중간 NxN 부분이 모두 1인지 확인
def check(new_lock):
    n = len(new_lock) // 3
    for i in range(n, n * 2):
        for j in range(n, n * 2):
            if new_lock[i][j] != 1:
                return False
    return True


def solution(key, lock):
    m = len(key)
    n = len(lock)
    # 기존 자물쇠보다 3배 큰 자물쇠
    new_lock = [[0] * (n * 3) for _ in range(n * 3)]
    # 새로운 자물쇠의 중앙 부분에 기존 자물쇠 넣기
    for i in range(n):
        for j in range(n):
            new_lock[n + i][n + j] = lock[i][j]

    # 열쇠를 (1, 1)부터 (N*2, N*2)까지 이동시키며 확인
    for i in range(1, n * 2):
        for j in range(1, n * 2):
            # 열쇠를 0, 90, 180, 270도로 회전시키며 확인
            for d in range(4):
                r_key = rotate(key, d)  # key를 d만큼 회전시킨 리스트
                for x in range(m):
                    for y in range(m):
                        new_lock[i + x][j + y] += r_key[x][y]

                if check(new_lock):
                    return True

                for x in range(m):
                    for y in range(m):
                        new_lock[i + x][j + y] -= r_key[x][y]

    return False