하루 2시간씩 시도해서 3~4일차에 완료했다. 다른 사람들 코드보면 100줄 이내던데, 난 191줄이다..ㅠㅠ
1. 아이디어
게임보드에서 빈칸들을 찾고 테이블에서 존재하는 모든 퍼즐조각을 찾는다. 각 빈칸에 대해 모든 퍼즐조각을 대입해본다. 만약 매칭이되면, 게임보드에서 퍼즐조각을 채우고, 테이블에서 해당 퍼즐조각을 지운다. 그리고 변수, answer에 해당 퍼즐조각 개수만큼 더하고 다음 게임보드의 빈칸으로 넘어간다. 만약 알맞는 퍼즐조각이 하나도 없다면, 테이블을 90도 회전하고 다시 퍼즐조각을 빈칸에 대입하여 매칭이되는지 확인해본다. 회전을 계속하여 동일한 테이블로 왔지만, 매칭되는 퍼즐조각을 찾지 못했다면 다음 게임보드의 빈칸으로 넘어간다
모든 빈칸에 대해 위의 방식을 적용하면 된다.
게임보드에서 빈칸을 찾아 저장하는 것은 bfs와 딕셔너리로 구현했다. 게임보드에서 처음보는 빈칸일 경우, 해당 좌표를 딕셔너리의 값으로 리스트에 추가하고 인접한 빈칸의 개수를 딕셔너리의 키로 설정했다. 테이블에 존재하는 모든 퍼즐조각도 같은 방식으로 구현했다.
퍼즐조각 매칭하는 것도 bfs로 구현했다. 만약 게임보드의 빈칸과 테이블의 퍼즐조각이 매칭이 된다면, 움직이는 방향이 동일하기 때문에 bfs로 구현할 수 있다.
매칭이 됐을 때, 테이블에서 퍼즐조각을 지우는 것도, 게임보드에서 퍼즐조각을 채우는 것도 전부 bfs로 구현했다. 각각의 함수에 대해 bfs를 별도로 구현했기 때문에 코드가 너무 길어졌다.
2. 코드
from collections import deque, defaultdict
r, c = 0, 0
d = ((0,1), (1,0), (-1,0), (0,-1))
board_visited = []
table_visited = []
tdict = defaultdict(list)
gdict = defaultdict(list)
def rotate(table):
global r, c
copy = [[-1 for _ in range(c)] for _ in range(r)]
q = deque()
for i in range(r):
for j in range(c):
q.append(table[i][j])
for j in range(c-1, -1, -1):
for i in range(r):
copy[i][j] = q.popleft()
return copy
def isin(y, x):
global r, c
if -1<y<r and -1<x<c: return True
return False
def find_empty_spaces(game_board, sy, sx):
global board_visited, gdict
q = deque()
q.append((sy, sx))
cnt = 1
while q:
y, x = q.popleft()
for dy, dx in d:
ny = y + dy
nx = x + dx
if not isin(ny, nx): continue
if not board_visited[ny][nx]:
board_visited[ny][nx] = True
if game_board[ny][nx] == 0:
cnt += 1
q.append((ny, nx))
gdict[cnt].append((sy, sx))
def _find_puzzles(table, sy, sx):
global table_visited, tdict
q = deque()
q.append((sy, sx))
cnt = 1
while q:
y, x = q.popleft()
for dy, dx in d:
ny = y + dy
nx = x + dx
if not isin(ny, nx): continue
if not table_visited[ny][nx]:
table_visited[ny][nx] = True
if table[ny][nx] == 1:
cnt += 1
q.append((ny, nx))
tdict[cnt].append((sy, sx))
def find_puzzles(table):
global table_visited, r, c, tdict
tdict = defaultdict(list)
table_visited = [[False for _ in range(c)] for _ in range(r)]
for i in range(r):
for j in range(c):
if not table_visited[i][j]:
table_visited[i][j] = True
if table[i][j] == 1: _find_puzzles(table, i, j)
def match_puzzle(gy, gx, ty, tx, table, game_board):
global board_visited, table_visited, r, c
board_visited = [[False for _ in range(c)] for _ in range(r)]
table_visited = [[False for _ in range(c)] for _ in range(r)]
board_visited[gy][gx] = True
table_visited[ty][tx] = True
match_count = 1
q = deque()
q.append((gy, gx, ty, tx))
while q:
gy, gx, ty, tx = q.popleft()
for dy, dx in d:
ngy = gy + dy
ngx = gx + dx
nty = ty + dy
ntx = tx + dx
if not isin(ngy, ngx) or not isin(nty, ntx): continue
if board_visited[ngy][ngx] or table_visited[nty][ntx]: continue
board_visited[ngy][ngx] = True
table_visited[nty][ntx] = True
if game_board[ngy][ngx] == 1 or table[nty][ntx] == 0: continue
match_count += 1
q.append((ngy, ngx, nty, ntx))
return match_count
def remove_puzzle(table, sy, sx):
global table_visited, r, c
table_visited = [[False for _ in range(c)] for _ in range(r)]
table[sy][sx] = 0
q = deque()
q.append((sy, sx))
table_visited[sy][sx] = True
while q:
y, x = q.popleft()
for dy, dx in d:
ny = y + dy
nx = x + dx
if not isin(ny, nx): continue
if not table_visited[ny][nx]:
table_visited[ny][nx] = True
if table[ny][nx] == 1:
table[ny][nx] = 0
q.append((ny, nx))
return table
def fill_puzzle(game_board, sy, sx):
global board_visited, r, c
board_visited = [[False for _ in range(c)] for _ in range(r)]
q = deque()
q.append((sy, sx))
board_visited[sy][sx] = True
game_board[sy][sx] = 1
while q:
y, x = q.popleft()
for dy, dx in d:
ny = y + dy
nx = x + dx
if not isin(ny, nx): continue
if not board_visited[ny][nx]:
board_visited[ny][nx] = True
if game_board[ny][nx] == 0:
game_board[ny][nx] = 1
q.append((ny, nx))
return game_board
def solution(game_board, table):
global table_visited, board_visited, tables, r, c
global gdict, tdict
r, c = len(table), len(table[0])
table_visited = [[False for _ in range(c)] for _ in range(r)]
board_visited = [[False for _ in range(c)] for _ in range(r)]
answer = 0
for i in range(r):
for j in range(c):
if not board_visited[i][j]:
board_visited[i][j] = True
if game_board[i][j] == 0: find_empty_spaces(game_board, i, j)
for i in range(1, 7):
if not gdict[i]: continue
while gdict[i]:
gy, gx = gdict[i].pop()
ok = False
ry, rx = -1, -1
for _ in range(4):
table = rotate(table)
find_puzzles(table)
for ty, tx in tdict[i]:
count = match_puzzle(gy, gx, ty, tx, table, game_board)
if count == i:
answer += i
ok = True
ry, rx = ty, tx
break
if ok: break
if ok:
table = remove_puzzle(table, ry, rx)
game_board = fill_puzzle(game_board, gy, gx)
return answer