(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
  1. game_board에서 빈칸의 좌표를 dfs로 구하고 해당 좌표를 0,0 위치를 기준으로 이동시킨다.
  2. table에서 블록의 좌표를 dfs로 구하고 해당 좌표를 0,0 위치를 기준으로 이동시킨다.
  3. 블록 좌표가 빈칸 좌표와 일치하면 빈칸 좌표를 지우고 이동칸만큼 answer에 더해준다.
  4. 해당 블록 좌표는 더이상 사용하면 안되므로 table을 업데이트 시켜준다.
  5. 만약 일치하지 않는다면 table을 원래대로 돌려놓는다.
  6. 2~5번 과정을 회전 횟수 4번만큼 반복한다.

© 2021. By Backtony