[프로그래머스] 자물쇠열쇠- Python

문제 설명

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

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

제한사항

• 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은 돌기 부분을 나타냅니다.

---

입출력 예

keylockresult

[[0, 0, 0], [1, 0, 0], [0, 1, 1]]

[[1, 1, 1], [1, 1, 0], [1, 0, 1]]

true

-----------------------------------------------------------------------------------------------------------------------------------

 

★ 시작하기 전에

어떤 식으로 풀어야 할지 많이 고민했다.

key는 회전이 가능하기 때문에, 총 4가지 경우의 모양의 key가 존재한다고 생각하자. (회전 알고리즘 생각)

그리고 위 4가지 중 하나씩 돌면서 하나씩 열쇠를 맞출수 잇는지 없는지를 판단한다.

우선, key의 나온 부분들로과 lock의 홈 부분이 일치해야한다.

즉! key의 튀어 나온 부분들 전부가 아닌 몇가지로 lock의 홈을 채우면 되는 것이다

 

N과 M 도 다르고 key를 상하좌우로 움직일 수 있는데 그러면 어떻게 매칭시킬 것인가?

>> 상대적인 위치 정보를 이용하자.

lock의 홈 정보를 절대 위치가 아닌 하나의 기준 홈을 주고 그에 대한 상대적인 위치 정보를 저장한다.

 

key의 튀어 나온 부분들을 하나씩 돌면서 기준 홈과 매칭시키고 나머지에 대해 상대적인 위치가 일치하는지를 비교하면 된다!

 

예시를 통한 분석 방법

 

1. 홈의 상대적인 정보를 저장한다.

기준 홈 str = (1, 2)

상대적 홈 정보 hom = [(1, -1)]

2. key의 튀어 나온 부분들을 하나씩 돌면서 상대 정보와 일치하는지 비교한다.

 - ① 부분을 기준 홈이라 생각한다.

 - 다른 튀어 나온 부분과의 상대 위치가 hom 리스트에 있는지 확인한다.

 - 아래의 경우, (1, 1), (1, 2) 모두 hom 리스트에 없으므로 매칭스킬 수 없다.

3. 90도 회전한 경우

 - ② 부분을 기준 홈과 매칭시킨다.

 - 다른 튀어 나온 부분의 상대위치인 (1, -1)는 hom에 있다.

 - 열쇠를 맞출 수 있으므로 true를 반환한다.

4. 추가적으로 생각해줘야할 것!

★★★ key의 상대적 위치가 hom에 없더라도 lock의 바깥에 위치하면 열쇠로 사용할 수 있음을 유의하자!

>> 조건 설정 필요!

 

답안 코드

def solution(key, lock):
    answer = False
    n = len(key)
    m = len(lock)
    
	# lock의 홈 정보와 상대 위치를 담는다.
    hom = []
    str = 0
    for i in range(m):
        for j in range(m):
            if lock[i][j] == 0:
                if str:
                    hom.append((str[0] - i, str[1] - j))
                else:
                    str = (i, j)
    
    cnt = 0
    isEnd = False
    # 4가지 key 경우이므로 while문 활용
    # hom이 없는 경우 무조건 true를 반환하도록 설정
    while hom and cnt <= 3:
    	
        # key의 튀어나온 부분을 ke라 하고 정보를 저장한다.
        ke = []
        for i in range(n):
            for j in range(n):
                if key[i][j] == 1:
                    ke.append((i, j))
                    
        # ke를 하나씩 기준 홈과 매칭시킨다.
        check = [0 for _ in range(len(ke))]
        for i in range(len(ke)):
            check[i] = 1
            str_key = ke[i]
            isTrue = True
            
            # 몇개의 홈이 채워졋는가? hom_cnt
            hom_cnt = 1
            for j in range(len(ke)):
                if check[j]: continue
                # 다른 ke를 하나씩 꺼내 그 상대 위치 gap을 구한다.
                nextR = ke[j][0]
                nextC = ke[j][1]
                gapR = str_key[0] - nextR
                gapC = str_key[1] - nextC
                
                # 기준 홈에 gap 위치가 lock의 범위를 벗어나는지 확인한다.
                if 0 <= str[0] - gapR < m and 0 <= str[1] - gapC < m:
                	# 상대 위치가 hom에 존재하는가 확인한다.
                    if (gapR, gapC) in hom:
                        hom_cnt += 1
                        continue
                    # 존재하지 않으면 모두 종료한다.
                    else:
                        isTrue = False
                        break
            # 종료되지 않고 hom_cnt가 모두 채워지면 true를 반환한다.
            if isTrue and hom_cnt == (len(hom)+1):
                answer = True
                isEnd = True
                break
            check[i] = 0
        
        # key 회전시키기
        tmp = key
        key = [[0 for _ in range(n)] for _ in range(n)]
        for r in range(n):
            for c in range(n):
                key[c][n-1-r] = tmp[r][c]
        if isEnd:
            break
        cnt += 1
        
    if not hom:
        answer = True
        
    return answer