0. 서문

간만에 일기를 적는다. 사실 일기 + 알고리즘 푼것 정리 개념으로 적는 느낌이었는데 알고리즘을 풀기만 하고 따로 올리지는 못했다. 이거 적을 시간에 차라리 빨리 기숙사 가서 씻고 자고싶다는 생각이 좀 간절하게 들때가 많아서...

Deltarune - Lancer's Theme [Electro Swing]

1. 자물쇠와 열쇠

https://programmers.co.kr/learn/courses/30/lessons/60059

이코테 책을 보면서 푼 문제였다. 어떻게 풀어야 할지 감도 안잡혀서 결국은 답지를 보면서 풀었다. 요 몇일은 네트워크 쪽 공부한다고 알고리즘을 아예 안풀어서 더더욱 그런걸지도...있는 기반도 없는데 몇일 안하니까 더 머리가 안돌아가는것같다.

해당하는 문제를 풀기위해서는 키를 90도로 돌리는 함수 와 이것이 맞는지 체크하는 함수를 따로 짜야했다.

추가로, 해당문제는 완전 탐색 문제였는데 완전 탐색을 더 수월하게 하기 위해서 자물쇠를 기존의 크기에서 3배로 만드는 과정을 넣고 자물쇠에 해당하는 부분이 정확히 1인지를 확인하는 식으로 푸는것이 이코테에서 푸는 방식이었다.

다만 꼭 3배여야 하나...?라는 의문점이 있어서 따로 다른 방식으로도 풀어보려한다.

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


def check(new_lock):
    lock_length = len(new_lock) // 3
    for i in range(lock_length, lock_length * 2):
        for j in range(lock_length, lock_length * 2):
            if new_lock[i][j] != 1:
                return False
    return True


def solution(key, lock):
    n = len(lock)
    m = len(key)

    new_lock = [[0] * (n * 3) for _ in range(n * 3)]

    for i in range(n):
        for j in range(n):
            new_lock[i+n][j+n] = lock[i][j]

    for rotation in range(4):
        key = rotate_a_matrix_by_90_degree(key)
        for x in range(n * 2):
            for y in range(n * 2):

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

                if check(new_lock) == True:
                    return True

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

    return False