[프로그래머스 Lv3.]자물쇠와 열쇠(python)

1. 문제

문제 설명

제한사항

입출력

입출력 예시

---

2. 풀이 과정

내가 생각한 진행 과정

• lock에 key를 넣었을 때 더 커지는 board를 만든다.
  • 입출력 예시에 따르면 아래와 같은 보드를 만드는 것이다
    [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]
• 이와 같은 보드를 만들면, lock을 가운데 고정시키고 key를 움직여 lock의 홈부분을 모두 채우는지 확인
• 하나의 key로 board의 처음부터 끝까지 방문한 후 rotation함수를 이용해 key를 90도 돌린다음, 다시 처음부터 끝까지 돌리기(총 4번 반복)
• board에서 key위치를 바꿔가며 채워지는지를 check함수로 확인
  • 채워지면 True 리턴
  • 채워지지 않으면, board판에 key 빼기
  • 하나의 key로 방문했을 때, 다 돌았다면 key를 rotation해주기
  • 끝까지 다 돌렸는데 홈을 매꾸지 못했으면 False 리턴

코드

def rotation(bd):
    n = len(bd)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            result[j][n-1-i] = bd[i][j]
    return result

def check(board, len_lock, len_key):
    for i in range(len_lock):
        for j in range(len_lock):
            if board[len_key + i][len_key + j] != 1:
                return False
    return True

def solution(key, lock):
    len_key = len(key)
    len_lock = len(lock)

    n = 2 * len_key + len_lock
    board = [[0] * n for _ in range(n)]

    for i in range(len_lock):
        for j in range(len_lock):
            board[len_key + i][len_key + j] += lock[i][j]
    # pprint(board)

    for time in range(4):  # 1번 key로 처음부터끝까지 돌리고, 2번key로 처음부터끝까지 돌리고..
        # board에 key 하나씩 넣어보기
        for i in range(1, len_key+len_lock):  # i, j는 board에 key 들어가는 시작점
            for j in range(1, len_key+len_lock):
                for x in range(len_key):  # x, y는 key안에서의 자리
                    for y in range(len_key):
                        board[i+x][j+y] += key[x][y]  # board판에 key 넣기

                # 채워지는 여부 확인
                if check(board, len_lock, len_key):
                    return True

                # key가 완벽하게 채워지지 않으면 board판에 key 빼기
                for x in range(len_key):
                    for y in range(len_key):
                        board[i + x][j + y] -= key[x][y]

        key = rotation(key)

    return False