자물쇠와 열쇠

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/60059#

프로그래머스

 

열쇠의 일부분만 자물쇠와 맞아도 되고, 대신 자물쇠의 모든 홈이 열쇠의 돌기와 맞아야 열리는 상황. 열쇠는 90도 회전이 가능하다.

 

자물쇠를 확장시켜서(최소 열쇠와 자물쇠의 한 칸은 겹치도록) 가능한 모든 케이스를 다 돌려봐도 괜찮다. N,M<=20이니까!

 

 

	def solution(key, lock):
	def rotate(mat): # 90도 회전 코드
	n = len(mat)
	m = len(mat[0])
	tmp = [[0]*n for _ in range(m)]
	for i in range(n):
	for j in range(m):
	tmp[j][n-i-1] = mat[i][j]
	return tmp
	m, n = len(key), len(lock)
	# 자물쇠 공간을 넓히고, 가운데 위치에만 lock 집어넣기
	# 이중 for문으로 key-lock 대응되는 모든 케이스 계산 가능
	extend = [[-1]*(n+2*(m-1)) for _ in range(n+2*(m-1))]
	num_groove = 0
	for i in range(n):
	for j in range(n):
	extend[m-1+i][m-1+j] = lock[i][j]
	if lock[i][j] == 0: num_groove += 1
	# 90도 회전시키면서(최대 4번) 맞아떨어지는 지점 있는지 체크
	for _ in range(4):
	key = rotate(key)
	for i in range(n+m-1):
	for j in range(n+m-1):
	# (i, j): key와 lock이 만나는 부분의 좌상단 좌표
	crash_flag = False # 현재 상태에서 key와 lock 충돌이 일어나는가?
	num_match = 0 # 홈-돌기 맞는 개수
	for x in range(m):
	for y in range(m):
	# 현재 자물쇠와 열쇠 홈/돌기
	cur_key = key[x][y]
	cur_lock = extend[i+x][j+y]
	if cur_lock == -1: continue # 실제 자물쇠 바깥, 확인 필요 X
	# key, lock이 (0,0) 또는 (1,1)이면 안 됨
	if cur_lock + cur_key == 1:
	if cur_lock == 0: # 자물쇠의 홈에 들어가는 갯수
	num_match += 1
	else: #여는 것이 불가능한 경우(홈-홈, 돌기-돌기)
	crash_flag = True
	break
	if crash_flag: break
	if not crash_flag and num_groove == num_match:
	return True
	return False

view raw 자물쇠와 열쇠.py hosted with ❤ by GitHub