[프로그래머스] Lv.3 자물쇠와 열쇠 - 파이썬(완전 탐색)

문제 출처 - https://programmers.co.kr/learn/courses/30/lessons/60059

• 완전 탐색이 가능한지 판단하기
• 행렬 회전 코드(코드 노트 추가)
• 최종 풀이

👌 완전 탐색이 가능한지 판단하기

문제를 처음 읽고 아무런 생각도 들지 않았다.
아직 풀어본 문제가 많지 않다보니 습관이 덜 들어있는 것 같다.
당장 풀이법이 떠오르지 않는다면 완전 탐색을 생각하고 시간내에
해결 가능한지 판단하자.

파이썬은 1초에 2000만에서 1억정도의 연산을 할 수 있다고 한다.
해당 문제는 가장 클 경우 20x20 2차원 배열을 2개 정도 사용하므로
완전탐색을 수행해도 충분히 해결할 수 있다.

자물쇠는 정사각형이며 0,1로 구성되는데 모든 항이 1이 되면 열리는 것으로 생각하면 된다. 따라서 먼저 모든 항이 1인지 체크하는 함수를 작성했다.

def check_solve(lock):
	for i in range(len(lock)):
   		for j in range(len(lock)):
           if lock[i][j] !=1:
           	   return False
	return True

그런데 막상 작성해놓고 생각하니 우리는 저기에 그냥 lock 배열이 아닌 열쇠와 합을한 배열을 넣어야하는데 열쇠 값을 기존 lock의 크기를 유지하며 그대로 넣는건 너무 복잡할 것 같았다.

그래서 key의 마지막행, 마지막열이 lock의 첫 행, 첫 열에 온다고 가정하며 key가 올 수 있는 범위만큼 확장된 2차원 배열에 lock 값을 넣어주는 함수를 새로 작성했다. 또 이에 따라 위의 체크 함수는 아래와 같이 변경하였다.

def make_new_lock(lock, key):
   length = len(lock)
   additional = key - 1
   new_lock = [[0] * (length + 2 * additional) for _ in range(length + 2 * additional)]
   for i in range(additional, length + additional):
       for j in range(additional, length + additional):
           new_lock[i][j] = lock[i - additional][j - additional]
   return new_lock

def check_solve(new_lock, key):
   additional = key - 1
   for i in range(additional, len(new_lock) - additional):
       for j in range(additional, len(new_lock) - additional):
           if new_lock[i][j] != 1:
               return False
   return True

이제 됐다. 만들어둔 함수를 가지고 lock으로 key에 따라 확장된 new_lock에다가 key값을 일일히 모든 위치에서 더해보며 new_lock의 lock 부분이 모두 1이 되는 경우만 찾으면 된다.
그렇게 완성한 내 첫 코드는 실패였다. 열쇠가 회전할 수 있다는 문제 정보를 제대로 인지하지 못한 탓이었다.

👌 완전 탐색이 가능한지 판단하기(코드노트 추가)

뭐가 문제인지 알았으니 MxN 행렬을 NxM 행렬로 바꾸는
즉, 시계방향으로 90도 회전하는 코드를 작성했다.

# a = m x n matrix -> n x m
def rotate_matrix90(a):
   m = len(a)  # 행 개수
   n = len(a[0])  # 열 개수
   result = [[0] * m for _ in range(n)]  # 결과 리스트 초기화
   for i in range(m):
       for j in range(n):
           result[j][m - 1 - i] = a[i][j]
   return result

코딩 테스트를 준비하는 분들이 본인만의 라이브러리 등을 만들어 둔다는 말을 들은적 있다. 그래서 앞으로 공부를 하면서 바로 구현하려면 꽤 머리아픈데 자주 쓰일만한 코드 들을 코드노트 라는 이름으로 따로 정리해서 관리하려고 한다.

코드노트 모음 - https://velog.io/@choi-ju12g/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%BD%94%EB%93%9C-%EB%85%B8%ED%8A%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC

🥇 최종 풀이

위의 직접 정의해둔 함수들을 이용하여 문제를 아래의 코드로 최종 해결하였다.

def solution(key, lock):
    new_lock = make_new_lock(lock,len(key))
    additional = len(key) -1
    length = len(lock)

    for ratate in range(4):
        key = rotate_matrix90(key)
        # 열쇠 이동
        for i in range(length+additional):
            for j in range(length+additional):

                # 위치에서 열쇠값 더하기
                for m in range(additional+1):
                    for n in range(additional+1):
                        new_lock[i+m][j+n] += key[m][n]

                if check_solve(new_lock,additional+1):
                    return True
                # print(m,"X",n,"위치")
                # print_mat(new_lock)
                # print("")
                # 자물쇠 다시 원상태로 복구
                for m in range(additional+1):
                    for n in range(additional+1):
                        new_lock[i+m][j+n] -= key[m][n]

    return False