[이코테 Ch12-10] 자물쇠와 열쇠 (구현)

👩🏻‍💻문제설명

[이코테 Ch12-10] 자물쇠와 열쇠 (구현)

✍️Idea Sketch

문제 요약

자물쇠와 회전, 이동이 가능한 열쇠가 있다.
목표 : 자물쇠의 모든 영역을 1로 채우기 = 자물쇠의 모든 홈을 채우기

열쇠 움직임 종류

1. 회전 : 시계방향 90도 (90도 함수 하나 만으로 180도, 270도 동작 가능)
2. 이동 : 상하좌우 1칸

중요 아이디어 : 자물쇠 배열 확장

시간복잡도

O(n^4), O(n^2 * m^2)
자물쇠와 열쇠의 최대 크기는 20 * 20으로, 시간 초과를 암시하는 연산횟수 1억과는 거리가 멀다. 따라서 브루트포스 알고리즘(완전 탐색)을 시도해봄직 하다.

이 문제는 자물쇠 배열을 3n * 3n으로 확장한 후, 가능한 모든 영역에 대해 열쇠 m * m 을 대조해봐야 한다. 따라서 자물쇠를 탐색함과 동시에 열쇠를 탐색하므로 O(n^2 * m^2) 이다. 일반적으로 표현하면 O(n^4) 으로, 실제로 사중 for문을 사용한다.

알고리즘 : 구현, 브루트포스 (완전 탐색)

문제 이해는 쉽지만 자물쇠 배열 확장이라는 아이디어를 떠올리지 못해 하드코딩만 하다가 고생고생한 문제이다. 열쇠의 회전, 자물쇠에 열쇠를 끼워 넣은 후 빼기 처럼 단순해 보이는 동작도 생각보다 구현하기 어려웠다.

✍️내 소스코드

• create_graph() : 자물쇠 배열을 3n * 3n으로 확장시키는 함수다. 3n * 3n 배열을 생성한 후, 가운데에 자물쇠를 배치한다.
• rotate() : 열쇠를 시계방향으로 90도 회전시킨다.
• unlock() : 가운데에 위치한 자물쇠의 모든 value가 1인지 확인한다.
• solution() : 메인 함수다. 사중 for문으로 자물쇠 배열 graph를 탐색함과 동시에 열쇠를 끼워 넣음 - unlock인지 확인 - 열쇠를 빼는 일련의 기능을 동작한다.

  def create_graph(n, lock):
      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


  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


  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)

      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]

                  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