-
[탐색] 자물쇠와 열쇠 (파이썬)코딩 테스트/프로그래머스 2023. 4. 25. 19:33
문제 설명
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
'코딩 테스트 > 프로그래머스' 카테고리의 다른 글
[파이썬] 풍선 터트리기 (0) 2023.05.03 [데브 매칭] 다단계 칫솔 판매 ( 파이썬 ) (0) 2023.04.26 [이분탐색] 입국심사 (파이썬) (0) 2023.04.22 [탐색] 경주로 건설 (파이썬) (0) 2023.04.22 [힙] 디스크 컨트롤러 (파이썬) (0) 2023.04.21 - 열쇠는 자물쇠 영역 밖으로도 나갈 수 있다는 것을 캐치