[프로그래머스/파이썬] 자물쇠와 열쇠(60059) 풀이

---

• 프로그래머스 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 프로그래머스 코딩테스트 연습
• 문제 링크: 자물쇠와 열쇠(60059)
• 문제풀이 코드 GitHub 링크
• 풀이 언어: Python 3

풀이

문제

열쇠 행렬을 회전/이동시켜 자물쇠의 모든 홈(0)을 정확히 메울 수 있는지 판별하는 문제입니다.

코드

def solution(key, lock):
    hole = 0
    for row in lock: hole += row.count(0)
    if hole == 0: return True

    for i in range(4):
##        print('======')
##        for row in key: print(*row)
##        print('======')
        for rStep in range(len(key)+len(lock)-1):
            for cStep in range(len(key)+len(lock)-1):
                if isMatched(key, lock, rStep, cStep, hole): return True
        key = rotateMatrixCW(key)
        
    return False

def isMatched(key, lock, rStep, cStep, hole):
    rStart = max(len(key) - rStep - 1, 0)
    rEnd = min(len(key), len(lock) + len(key) - rStep - 1)
    rLockStart = max(0, rStep - len(key) + 1)
    
    cStart = max(len(key) - cStep - 1, 0)
    cEnd = min(len(key), len(lock) + len(key) - cStep - 1)
    cLockStart = max(0, cStep - len(key) + 1)

##    print(f'rStep:{rStep}, rStart: {rStart}, rEnd: {rEnd}, rlockStart: {rLockStart}, cStep:{cStep}, cStart: {cStart}, cEnd: {cEnd}, clockStart: {cLockStart}, hole: {hole}')

    matched = True
    cnt = 0
    for i in range(rStart, rEnd):
        for j in range(cStart, cEnd):
##            print(f'key: ({i}, {j}, lock:({rLockStart+i-rStart}, {cLockStart+j-cStart}))')
            matched &= key[i][j] !=\
                       lock[rLockStart+i-rStart][cLockStart+j-cStart]
            if key[i][j] == 1 and\
               lock[rLockStart+i-rStart][cLockStart+j-cStart] == 0: cnt += 1
                
##    print(matched, cnt)
    return matched and cnt == hole

def rotateMatrixCW(mat):
    result = []
    for i in range(len(mat)):
        row = []
        for j in range(len(mat)-1, -1, -1):
            row.append(mat[j][i])
        result.append(row)
    return result

#print(solution([[0, 0, 0], [1, 0, 0], [0, 1, 1]],[[1, 1, 1], [1, 1, 0], [1, 0, 1]]))
##print(solution([[0, 0, 0, 0], [1, 0, 0, 0], [0, 1, 0, 0], [1, 0, 0,1]], [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 0], [1, 1, 1, 0, 1]]))

설명

열쇠를 4번 회전시키며, 가능한 모든 이동 위치에 대해 자물쇠와 겹치는 영역만 비교합니다.

검증 조건은 두 가지입니다.

• 겹치는 모든 칸에서 값이 서로 달라야 함(돌기-홈)
• 자물쇠의 홈 개수와 정확히 같은 수의 홈이 메워져야 함

하나라도 만족하면 True, 끝까지 없으면 False를 반환합니다.

---

• 프로그래머스 문제풀이 전체 목록 보기

---