[programmers 60059] 2020 공채 3번 자물쇠와열쇠

문제

[programmers 60059] 자물쇠와열쇠

접근법

M,N이 20이 이하이므로 완전 탐색 쓰기!

전체 흐름

for 90도씩 회전:
	# key 반시계방향으로 돌리기
    for key 한칸씩 이동하며 자물쇠 홈 채우기:
    	# 딱 맞으면 True 리턴

# 딱 맞는 경우가 없으면 False 리턴

코드

def solution(key, lock):
    M,N = len(key),len(lock) # 3<=M<=N<=20
    
    # lock길이의 3배인 board를 만들어 가운데를 lock값으로 초기화
    board = [ [0]*3*N for _ in range(3*N) ]
    for i in range(N):
        for j in range(N):
            board[N+i][N+j]=lock[i][j]
           
     
    newkey = [ [0]*M for _ in range(M)] 
    
    # key 90도씩 회전시키고 모든 경우에 대하여 홈 채우기
    for dir in range(4):
        
        # key 반시계방향으로 돌리기
        for i in range(M):
            for j in range(M):
                newkey[i][j] = key[j][M-1-i]
      
        ### 한칸씩 이동하며 홈 채우기
        for X in range(N-M+1,2*N): #N-M+1부터 2*N-1까지
            for Y in range(N-M+1,2*N):
                
                newboard = [ board[i][:] for i in range(3*N) ]  # 처음 board 값 복사
                
                # 자물쇠에 열쇠 끼워넣기
                for i in range(M):
                    for j in range(M):
                        newboard[X+i][Y+j] += newkey[i][j]
                
                # 딱 맞는지 체크
                check = 0
                for i in range(N,2*N):
                    for j in range(N,2*N):
                        if newboard[i][j]==1: 
                            check += 1
                if check==N**2:
                    return True
                
        key = [ newkey[i][:] for i in range(M) ]  # key에 현재 newkey값 복사해야 이따 재활용할 수 있음
 
    return False

실수한 점

'딱 맞는지 체크'하는 부분을 다음과 같이 잘못 짰다.

# 딱 맞는지 체크
if sum(map(sum,newlock))==(N**2):
    return True

이 코드는 자물쇠와 열쇠가 모두 돌기인 경우(newboard[i][j]==2)를 고려하지 못한 코드다

따라서 다음과 같이 바꿔주었다

# 딱 맞는지 체크
check = 0
for i in range(N,2*N):
    for j in range(N,2*N):
    # 정확히 1일 때만
    if newboard[i][j]==1: 
        check += 1
if check==N**2:
    return True

결과