from collections import deque,defaultdict
dx = [0,0,1,-1]
dy = [1,-1,0,0]
# 초점 정렬
def realloc(fig):
xMin = sorted(fig,key=lambda x:(x[0]))[0][0]
yMin = sorted(fig,key=lambda x:(x[1]))[0][1]
for f in fig:
f[0] -= xMin
f[1] -= yMin
fig.sort(key=lambda x:(x[0],x[1]))
def rotate(fig):
newFig=[]
rotateFig =[]
# 영점 조준
realloc(fig)
for f in fig:
rotateFig.append([f[1],-f[0]])
# 영점 조준
realloc(rotateFig)
return rotateFig
# 매트릭스 도형 파악
def findFigs(metrix,isTable):
n = len(metrix)
visited = [[False for _ in range(n)] for _ in range(n)]
q = deque()
results = []
for i in range(n):
for j in range(n):
if visited[i][j] == True:
continue
# dfs start
if metrix[i][j] == isTable:
result = []
q.append((i,j))
visited[i][j]=True
result.append([i,j])
while q:
x,y = q.pop()
for z in range(4):
nx = x + dx[z]
ny = y + dy[z]
if 0 <= nx < n and 0 <= ny < n:
if visited[nx][ny]==False and metrix[nx][ny]==isTable:
visited[nx][ny] = True
result.append([nx,ny])
q.append((nx,ny))
realloc(result)
results.append(result)
# dfs end
return results
def solution(game_board, table):
answer = 0
tableBlocks = {}
boardBlocks = {}
tableBlocksFinish = [] # blockIds
boardBlocksFinish = []
for idx, block in enumerate(findFigs(table,1)):
tableBlocks[idx] = block
for idx, block in enumerate(findFigs(game_board,0)):
boardBlocks[idx] = block
for k1,v1 in boardBlocks.items():
for k2,v2 in tableBlocks.items():
for i in range(4):
v2 = rotate(v2)
if v1 == v2 and not (k1 in boardBlocksFinish) and not (k2 in tableBlocksFinish):
answer+=len(v1)
boardBlocksFinish.append(k1)
tableBlocksFinish.append(k2)
break
return answer