[이것이 코딩 테스트다 with Python] Chapter 12. 구현 - 자물쇠와 열쇠

< 자물쇠와 열쇠 >

 

💬 문제 설명

고고학자인 튜브는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 현태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해주는 종이가 발견되었습니다.
....

 

입력 (key)	입력(lock)	출력(result)
[[0, 0, 0], [1, 0, 0], [0, 1, 1]]	[[1, 1, 1], [1, 1, 0], [1, 0, 1]]	true

💬 입력 조건

• key는 M x M ( 3 ≤ M ≤ 20. M은 자연수 ) 크기 2차원 배열.
• lock은 N x N ( 3 ≤ N ≤ 20. N은 자연수 ) 크기 2차원 배열.
• M 은 N 이하이다.
• key와 lock의 원소는 0, 1 로 이루어짐. ( 0은 홈, 1은 돌기 )
  
  

💬 출력 조건

• 열쇠를 열 수 있으면 true, 열지 못하면 false

---

✍ 문제요약

key와 lock이 0(홈), 1(돌기)로 이루어진 2차원 배열로 주어지는데, 실제 열쇠처럼 자물쇠를 열 수 있는지 판단해야 한다. 이 때 열쇠는 회전과 이동이 가능하다. lock의 0(홈)에 key 1(돌기)가 딱 맞게 들어가는 케이스가 있다면 true(열 수 있다), 그러한 케이스가 없다면false(열 수 없다)를 출력한다. 

💯 문제링크

프로그래머스의 "자물쇠와 열쇠"와 동일한 문제이다.

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

프로그래머스

---

✅  문제 풀이

• key가 이동과 회전이 가능하기 때문에 확인해야할 case가 굉장히 많다.
• key 시계방향 90도 회전 ( 2차원 배열 회전 시키기 )
  
  
  • 2차원 배열을 역순으로 바꾼다.
    

    key = [[0,0,0],[1,0,0],[0,1,1]]
    
    key = key[::-1]
    print(key)
    # [[0, 1, 1], [1, 0, 0], [0, 0, 0]]​

     
  • zip 함수를 사용한다.
  • 배열이 tuple 이기 때문에 list로 변형
    

    key = [[0,0,0],[1,0,0],[0,1,1]]
    
    key = list(map(list,zip(*key[::-1])))
    for lst in key : print(lst)
    # [0, 1, 0]
    # [1, 0, 0]
    # [1, 0, 0]

• key의 이동
  
  
  • 가로, 세로 방향으로 lock의 길이의 -1 만큼 이동 가능하다.
  • lock의 길이가 3이면 -2 ~ 2 만큼 이동하면 된다. ( 3을 이동하면 key가 lock을 벗어남 )
• 주의 해야할 조건
  
  
  • 잘물쇠 영역 내에서 lock의 홈(0)에는 무조건 key의 돌기(1)가 필요하다.
  • 잘물쇠 영역 내에서 lock의 돌기(1)에는 key의 돌기(1)가 와서는 안된다.
  • 잘물쇠 영역 밖에서는 key의 돌기(1)와 홈(0)은 영향을 주지 않는다. 
• 위 내용을 주의 하면서 4번의 회전과, 모든 케이스의 이동을 완전 탐색한다.

# key를 회전 시켜야함 (3회전)
# key의 4가지 케이스 전부 완탐
# 이동은?

def solution(key, lock):
    M = len(key) # key 길이
    N = len(lock) # lock 길이
    
    def check(key_rotate, dr, dc):
        Open = True
        for r in range(N):
            for c in range(N):
                nr, nc = r - dr, c - dc       
                # r, c는 lock을 확인
                # nr, nc는 dr, dc만큼 이동한 key를 확인
                
                if 0 <= nr < M and 0 <= nc < M:              # lock위치에 key가 있으면
                    if lock[r][c] == key_rotate[nr][nc]:     # 홈(0)과홈(0) X, 돌기(1)와 돌기(1) X 
                        return False
                elif not (0 <= nr < M) or not (0 <= nc < M): # lock위치에 key가 없으면
                    if lock[r][c] == 0:                      # 홈(0)이면 열수없음, 돌기(1)는 상관없음
                        return False
        return True
            
    for _ in range(4):                   # 4번의 회전
        for dr in range(1 - N, N):       # 세로 이동
            for dc in range(1 - N, N):   # 가로 이동
                if check(key, dr, dc):   # 이 case가 true면 열수 있다는 의미
                    return True          
        key = list(map(list,zip(*key[::-1]))) # 시계방향 90도 회전
    return False