[탐색] 자물쇠와 열쇠 (파이썬)

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/60059

프로그래머스

문제 풀이

• 열쇠는 자물쇠 영역 밖으로도 나갈 수 있다는 것을 캐치
  • 열쇠의 [n-1,n-1] 좌표가 자물쇠의 [0,0]에 닫을 수 있음
  • 열쇠의 [0,0]이 자물쇠의 [m-1,m-1]에 닿을 수 있음
• 이 점을 해결하기 위해서는 자물쇠의 가로 세로를 3씩 곱해서 늘려줘야함
• 그런 다음 열쇠를 자물쇠의 오른쪽, 아래 방향씩 탐색하면 됨(방문 체크는 sx,sy 라는 시작 지점을 통해 체크)
• 큐에는 시작x, 시작y, 끝x, 끝y, x방향 이동 횟수, y방향 이동 횟수 를 담아줌
  • q => sx, sy, ex, ey, x, y
• 시작과 끝은 9배로 커진 lock의 탐색 지점들을 뜻하는 것이고, x와y는 key 좌표와 비교하기 위해 넣어줌
• lock[a][b] , key[a-x][b-y]  비교

소스 코드

# 열쇠의 돌기(1)-> 자물쇠 홈(0) 0
# 자물쇠 영역 안에선 열쇠의 돌기(1) -> 자물쇠 돌기(1) x

from copy import deepcopy
from collections import deque

dx = [1,0] #아래, 오른쪽
dy = [0,1]

def solution(key, lo):
    m,n = len(key),len(lo) 
    result = 0	#자물쇠 0 갯수
    for i in range(n): 
        result+=lo[i].count(0)
    
    temp = [[-1]*3*n for i in range(3*n)] 	#자물쇠 크기 *3*3
    for i in range(n):
        for j in range(n):
            temp[i+n][j+n]=lo[i][j]
    lock = deepcopy(temp)
    
    for rotation in range(4):   	#열쇠 돌려주는 작업
        if rotation!=0:
            temp = [[0]*m for i in range(m)]
            for j in range(m):
                for i in range(m):
                    temp[i][j] = key[m-1-j][i]
            key=deepcopy(temp)
            
            		    
        visited = [[False]*3*n for i in range(3*n)]		#열쇠 돌려줄때마다 방문 체크 새로 만들기
        visited[0][0]=True
        q = deque()
        q.append((0,0,m,m,0,0))
        while(q):
            sx,sy,ex,ey,x,y= q.popleft()		# x,y는 dx,dy로 몇 번 이동했는지 담겨져있음
            tri = False
            cnt = 0
            for i in range(sx,ex):
                for j in range(sy,ey):
                    if lock[i][j]==1 and key[i-x][j-y]==1:
                        tri= True
                        break
                    if lock[i][j]==0 and key[i-x][j-y]==1:
                        cnt+=1
                if tri==True:
                    break
            
            
            if tri==False and cnt==result:
                return True
            else:
                for k in range(2):
                    nsx = sx+dx[k]
                    nex = ex+dx[k]
                    nsy = sy+dy[k]
                    ney = ey+dy[k]
                    if nex>=3*n or ney>=3*n :
                        continue
                    if visited[nsx][nsy]==True:
                        continue
                    visited[nsx][nsy] = True
                    q.append((nsx,nsy,nex,ney,x+dx[k],y+dy[k]))
                        
    

    return False