이코테(구현) - 자물쇠와 열쇠

문제설명 

한 칸의 크기가 1 x 1인 N x N 크기의 정사각 형태 자물쇠와 M x M 크기인 정사각형태 열쇠가 주어짐

열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다.

자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않음 

자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 함

 

열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 구현

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

프로그래머스

 

효율성 체크 및 접근 방법

자물쇠와 열쇠의 크기는 20 x 20보다 작다. 

크기가 20x20인 2차원 리스트에 있는 모든 원소에 접근 할 때는 400만큼의 연산 필요

파이썬의 경우 보통 1초에 2000만 ~ 1억정도 연산처리 가능

(자물쇠 20x20 열쇠 20x20 라고 하면 -> 160000 연산)

-> 완전 탐색을 이용해서 열쇠를 이동이나 회전 시켜서 자물쇠에 끼워보는 작업을 전부 시도해보는 접근방법 이용.

시간복잡도: 자물쇠를 탐색함과 동시에 열쇠를 탐색하므로 O(n^2 * m^2) 이다. 일반적으로 표현하면 O(n^4) 으로, 실제로 사중 for문을 사용한다.

 

풀이

- 열쇠를 적당히 회전하고 이동시켜 자물쇠의 홈에 딱 맞게 끼워 넣어야 한다.

- 자물쇠 리스트의 크기를 3배 이상으로 변경하여 중앙 부분에 자물쇠를 놓는다

- 열쇠 배열을 왼쪽 위부터 시작해서 한 칸 씩 이동하는 방식으로 차례로 자물쇠 모든 홈을 채울 수있는지 확인

- 자물쇠 리스트에 열쇠 리스트 값을 더한 후 자물쇠 부분의 모든 값이 정확히 1인지 확인한다.

 

 

파이썬 코드

 # 자물쇠의 크기를 기존의 3배로 변환
 def create_graph(n, lock):
      #자물쇠 크기 *3
      graph = [[0] * (n*3) for _ in range(n * 3)]
      #새로운 자물쇠의 중앙부분에 기존의 자물쇠 넣기
      for i in range(n):
          for j in range(n):
              graph[i + n][j + n] = lock[i][j]
      return graph
 
  # 자물쇠의 중간 부분이 모두 1인지 확인
  def unlock(n, graph):
      for i in range(n, n * 2):
          for j in range(n, n * 2):
              if graph[i][j] != 1:
                  return False
      return True
 
  #2차원 리스트 90도 회전
  def rotate(m, key):
      nkey = [[0] * m for _ in range(m)]
      for i in range(m):
          for j in range(m):
              nkey[j][-i + m - 1] = key[i][j]
      return nkey
 
 
  def solution(key, lock):
      n, m = len(lock), len(key)
      graph = create_graph(n, lock)
 
      #4가지 방향에 대해서 확인
      for _ in range(4):  # 90, 180, 270, 360
          key = rotate(m, key)
          #열쇠 배열을 자물쇠 배열의 왼쪽 위부터 시작해서 한 칸씩 이동하여 확인
          for x in range(n * 2):
              for y in range(n * 2):
                  #자물쇠에 열쇠 끼워넣기
                  for i in range(m):
                      for j in range(m):
                          graph[x + i][y + j] += key[i][j]
                  #정확히 들어맞는지 검사(모든요소가 1)
                  if unlock(n, graph):
                      return True
                  #자물쇠에서 열쇠 다시 빼기
                  for i in range(m):
                      for j in range(m):
                          graph[x + i][y + j] -= key[i][j]
 
      return False

 

-참고:  2차원 리스트 90도 회전

위의 그림에서 알 수 있는 부분은 90도 회전에서는 1행이 5열로 이동, 2행이 4열로 이동, 4행이 3열로 이동..

따라서 정리 index(row, col)를 정리하면 아래와 같습니다.

(0,0), (0,1), (0,2),... , (0,4)  => (0,4), (1,4), (2,4),... (4,4)

규칙을 찾아내 보면, 다음과 같습니다.

회전 후의 행(row) index는 기존 열 index가 됩니다.
회전 후의 열(col) index는 기존 행, 열 마지막 index(4)에서 기존 행 index(0)을 뺀 값이 됩니다.

 

 

 

 

참고자료

https://aeroej.tistory.com/163

https://tasddc.tistory.com/108