[programmers 84021] 퍼즐조각채우기
네이버 기출로도 알려진 퍼즐조각채우기를 풀어보았다
문제 접근 방식
- table의 블럭을 bfs로 탐색한다.
(이 때 처음 좌표를 (0,0)으로 두고 그 다음 좌표는 상대적인 좌표를 저장한다)- game_board의 빈칸도 bfs로 탐색한다(마찬가지로 상대적인 좌표)
- 이 때 bfs의 결과( (x,y) 좌표들)를 0이상의 값으로 바꿔 통일시켜 주었다
# 1. table에서 block찾기
blocks = []
for i in range(l2):
for j in range(l2):
if table[i][j]==1:
blocks.append( revise( bfs(i,j,table,l2,1) ) ) # 3.
# 2. game_board에서 blank찾기
blanks = []
for i in range(l1):
for j in range(l1):
if game_board[i][j]==0:
blanks.append( revise( bfs(i,j,game_board,l1,0) ) ) # 3.
# blocks를 90도씩 회전한 좌표값 저장할 rotated_blocks(3차원) 생성
rotated_blocks = [ blocks[:] ] # deepcopy # [ [blocks], [blocks 90도회전], ... ] (3차원배열)
for rot in range(4):
# 3.
rotated_blocks.append( [ revise([(b[1],-b[0]) for b in block]) for block in rotated_blocks[rot]] )
예를 들어, 예제 1을 보면
game_board의 ㅗ 모양과 table의 ㅓ 모양은 분명 같은 모양인데
ㅓ 모양을 아무리 돌려도 ㅗ모양의 좌표값과 맞지 않는다.
# 한 블록의 모든 (x,y)에 대하여 0이상 값을 갖도록 보정
def revise(pos):
MIN_x, MIN_y = min(p[0] for p in pos), min(p[1] for p in pos)
newpos = [ (p[0]-MIN_x,p[1]-MIN_y) for p in pos]
return newpos
revise 함수로 모든 좌표값이 0이상의 값을 갖도록 바꿔주면 좌표값을 통일시킬 수 있다.
전체 코드
from collections import deque
def solution(game_board, table):
l1 = len(game_board)
l2 = len(table)
dx = [0,0,1,-1] # 동서남북
dy = [1,-1,0,0]
# 한 블록의 모든 (x,y)에 대하여 0이상 값을 갖도록 보정
def revise(pos):
MIN_x, MIN_y = min(p[0] for p in pos), min(p[1] for p in pos)
newpos = [ (p[0]-MIN_x,p[1]-MIN_y) for p in pos]
return newpos
def bfs(i,j,graph,L,N):
q = deque()
q.append((i,j))
graph[i][j]=-1 # 방문했다는 표시
pos = [ (0,0) ] # 블럭의 위치를 저장하는 배열(처음 (i,j)를 (0,0)으로 세팅)
while q:
x,y = q.popleft()
for dir in range(4):
nx,ny = x+dx[dir],y+dy[dir]
if nx>=L or nx<0 or ny>=L or ny<0: continue
if graph[nx][ny]==-1: continue # 이미 방문한 칸이면
if graph[nx][ny]!=N: continue # 탐색할 칸이 아니면
q.append( (nx,ny) )
graph[nx][ny]=-1
pos.append( (nx-i,ny-j) ) # 처음 (i,j)에 대한 상대적인 위치
return pos
def find(_blank):
for dir in range(4):
for k in range(len(blocks)):
block = rotated_blocks[dir][k]
if used[k]: continue # k번째 블록 이미 썼으면 넘어가기
if len(_blank)!=len(block): continue # 길이 다르면 넘어가기
# block 같으면
if set(_blank)==set(block):
used[k]=True
return len(_blank)
# 맞는 block 없으면 0 리턴
return 0
# table에서 block찾기
blocks = []
for i in range(l2):
for j in range(l2):
if table[i][j]==1:
blocks.append( revise( bfs(i,j,table,l2,1) ) )
# game_board에서 blank찾기
blanks = []
for i in range(l1):
for j in range(l1):
if game_board[i][j]==0:
blanks.append( revise( bfs(i,j,game_board,l1,0) ) )
# blocks를 90도씩 회전한 좌표값 저장할 rotated_blocks(3차원) 생성
rotated_blocks = [ blocks[:] ] # deepcopy # [ [blocks], [blocks 90도회전], ... ] (3차원배열)
for rot in range(4):
rotated_blocks.append( [ revise([(b[1],-b[0]) for b in block]) for block in rotated_blocks[rot]] )
# game_board의 각각의 blank에 대하여 맞는 block 찾기
answer = 0
used = [False]*len(blocks) # 각각의 block이 사용되었는지 # 블록 썼으면 True, 아직 안썼으면 False
for blank in blanks:
answer += find(blank)
return answer
print(solution([[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]], [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]])) # 14
노트
다른 사람 풀이를 보니, 90도 회전을 나처럼
[(b[1],-b[0]) for b in block]
로 처리하는 게 아니라
table을 아예 통째로 돌리면 좌표값 0 이상이 되도록 보정할 필요없다
Author And Source
이 문제에 관하여([programmers 84021] 퍼즐조각채우기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@savannah030/programmers-84021-퍼즐조각채우기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)