[ programmers] 구현 - 자물쇠와 열쇠

문제 링크

코딩테스트 연습 - 자물쇠와 열쇠

문제 해설

MM의 열쇠와 NN 자물쇠가 주어질때, 열쇠를 회전/이동하여 열쇠의 돌기부분을 자물쇠의 홈 부분에 정확히 일치시킬 수 있는지 확인하기 (홈은 0, 돌기는 1)

→ 회전/이동시

• 자물쇠 영역 밖: 상관 x
• 자물쇠 영역 안: 자물쇠의 모든 홈을 열쇠의 돌기가, 자물쇠의 돌기 튀어나온 부분에 열쇠의 돌기 튀어나오면 x

IN
key : MM크기의 2차원 배열
lock : NN크기의 2차원 배열

OUT
회전/이동을 자물쇠를 풀 수 있으면 true, 아니면 false

문제풀이

시도 1

import copy

def goup(key):
    for i in range(len(key)-1):
        key[i] = key[i+1]
    key[len(key)-1] = [-1 for i in range(len(key))]
    
def godown(key):
    for i in range(len(key)-1, 0, -1):
        key[i] = key[i-1]
    key[0] = [-1 for i in range(len(key))]
    
def goright(key):
    for i in range(len(key)):
        key[i].insert(0,-1)
        key[i].pop()
def goleft(key):
    for i in range(len(key)):
        key[i].append(-1)
        key[i].pop(0)

def checkTrue(key, lock):
    for i in range(len(lock)):
        for j in range(len(lock)):
						#자물쇠의 돌기와 열쇠의 돌기 둘다 튀어나온 경우
            if lock[i][j] == 1 and key[i][j] == 1:
                return False
						#자물쇠의 홈 부분에 열쇠의 돌기가 튀어나오지 않은 부분
            elif lock[i][j] == 0 and key[i][j] != 1:
                return False
    return True

def solution(key, lock):
    answer = False
    rotated = copy.deepcopy(key)
    #print(rotated)
    
    if all(0 not in l for l in lock):
        return True
    if checkTrue(rotated, lock):
        return True
    
    for step in range(4):
        #상하좌우 찾기
        tmp1 = copy.deepcopy(rotated)
        for i in range(len(key)):
            tmp2 = copy.deepcopy(tmp1)
            for j in range(len(key)-1):
                goleft(tmp2)
                #print("left: ", tmp2)
                if checkTrue(tmp2, lock):
                    return True
            tmp2 = copy.deepcopy(tmp1)
            for j in range(len(key)-1):
                goright(tmp2)
                #print("right: ", tmp2)
                if checkTrue(tmp2, lock):
                    return True
            goup(tmp1)
            #print("up: ", tmp1)
            if checkTrue(tmp1, lock):
                return True

        tmp1 = copy.deepcopy(rotated)
        #print("\n\n", tmp1)
        for i in range(len(key)):
            tmp2 = copy.deepcopy(tmp1)
            for j in range(len(key)-1):
                goleft(tmp2)
                #print("left: ", tmp2)
                if checkTrue(tmp2, lock):
                    return True
            tmp2 = copy.deepcopy(tmp1)
            for j in range(len(key)-1):
                goright(tmp2)
                #print("right: ", tmp2)
                if checkTrue(tmp2, lock):
                    return True
            godown(tmp1)
            #print("down: ", tmp1)
            if checkTrue(tmp1, lock):
                return True

        #시계방향으로 회전
        tmpkey = []
        for i in range(len(key)):
            tmp = []
            for j in range(len(key)):
                tmp.append(rotated[len(key)-j-1][i])
            tmpkey.append(tmp)
        rotated = copy.deepcopy(tmpkey)

        #print(rotated)
    
    return answer

0도부터 90, 270, 360도로 열쇠를 회전한 후, 상하좌우로 한칸씩 직접 이동해 자물쇠를 풀 수 있는지 검사하였다. 하지만 절반 넘는 테케에서 런타임 에러가 발생하였다 . ㅜ ㅜ

시도 2

def rotate_a_matrix_by_90_degrees(a):
    n = len(a)
    m = len(a[0])
    result = [[0]*n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            result[j][n-i-1] = a[i][j]
    return result

#자물쇠의 중간부분이 모두 1인지?
def check(new_lock):
    lock_length = len((new_lock)) // 3
    for i in range(lock_length, lock_length*2):
        for j in range(lock_length, lock_length*2):
            if new_lock[i][j] != 1:
                return False
    return True

def solution(key, lock):
    n = len(key)
    m = len(lock)
    new_lock = [[0]*(m*3) for _ in range(m*3)]

		#자물쇠가 모두 1일때의 경우
    if all(0 not in l for l in lock):
        return True

    for i in range(m):
        for j in range(m):
            new_lock[i+m][j+m] = lock[i][j]

    for rotation in range(4):
        key = rotate_a_matrix_by_90_degrees(key)
        for x in range(m*2):
            for y in range(m*2):
                for i in range(n):
                    for j in range(n):
                        new_lock[x+i][y+j] += key[i][j]
                if check(new_lock) == True:
                    return True
                for i in range(n):
                    for j in range(n):
                        new_lock[x+i][y+j] -= key[i][j]
    return False

풀이를 보니 리스트를 직접 조작하는것이 아닌 자물쇠 크기3의 2차원 배열을 만들어서 nn씩 자물쇠와 비교를 하였다. 내꺼도 어캐 바꾸면 될거같은데 ,,

알게된 것

• 리스트의 깊은 복사

위키독스

import copy

#deep copy
#내부의 객체들까지 전부 새로 생성 -> tmp1 수정시에도 rotated는 바뀌지 x
tmp1 = copy.deepcopy(rotated)

#shallow copy
tmp1 = rotated[:]
tmp1 = copy.copy(rotated)

• 2차원 리스트 원소 포함 여부

#lock에 0이 존재하지 않는지?
if all(0 not in l for l in lock):
        return True

#lock에 0이 하나라도 존재하는지?
if any(0 in l for l in lock):
        return True