(Python) 프로그래머스 - 퍼즐 조각 채우기
in Algorithm on Programmers, Level3
[문제 링크]
풀이
import copy
def solution(game_board, table):
n = len(game_board)
answer = 0
# game_board의 빈칸 좌표를 구해서 0,0좌표를 기준으로 옮기기
blank = []
for i in range(n):
for j in range(n):
if game_board[i][j] == 0:
blank.append(dfs(game_board, i, j, [0, 0], n, 0))
for k in range(4):
table = rotate(table)
copy_table = copy.deepcopy(table)
for i in range(n):
for j in range(n):
if copy_table[i][j] == 1:
block = dfs(copy_table, i, j, [0, 0], n, 1)
if block in blank:
blank.remove(block)
answer += len(block)
table = copy.deepcopy(copy_table)
else:
copy_table = copy.deepcopy(table)
return answer
# position은 기준이 되는 좌표 -> 0,0으로 옮기기 위한 기준이 되는 좌표
def dfs(board, x, y, position, n, num):
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
result = [position]
board[x][y] = 2 # 방문처리
for i in range(4):
px = x + dx[i]
py = y + dy[i]
if 0 <= px and px < n and 0 <= py and py < n:
if board[px][py] == num:
result += dfs(board, px, py, [position[0] + dx[i], position[1] + dy[i]], n, num)
return result
# 회전
def rotate(table):
n = len(table)
rotated = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
rotated[j][n - i - 1] = table[i][j]
return rotated
- game_board에서 빈칸의 좌표를 dfs로 구하고 해당 좌표를 0,0 위치를 기준으로 이동시킨다.
- table에서 블록의 좌표를 dfs로 구하고 해당 좌표를 0,0 위치를 기준으로 이동시킨다.
- 블록 좌표가 빈칸 좌표와 일치하면 빈칸 좌표를 지우고 이동칸만큼 answer에 더해준다.
- 해당 블록 좌표는 더이상 사용하면 안되므로 table을 업데이트 시켜준다.
- 만약 일치하지 않는다면 table을 원래대로 돌려놓는다.
- 2~5번 과정을 회전 횟수 4번만큼 반복한다.