[프로그래머스] 퍼즐 조각 채우기

박형진·2022년 2월 20일
0

https://programmers.co.kr/learn/courses/30/lessons/84021


1. 전체 코드

from collections import defaultdict


def solution(game_board, table):
    answer = []
    length = len(table)
    blanks = defaultdict(list)

    def rotate(arr):
        n = len(game_board)
        r = []
        for x, y in arr:
            r.append((y, n - 1 - x))
        return r

    def check(u, v, l):
        for i in range(l - 1):
            if u[i + 1][0] - u[i][0] != v[i + 1][0] - v[i][0]:
                return False
            if u[i + 1][1] - u[i][1] != v[i + 1][1] - v[i][1]:
                return False
        return True

    def dfs(x, y, matrix):
        k = 1 if matrix == table else 0
        if 0 <= x < length and 0 <= y < length and matrix[x][y] == k:
            matrix[x][y] = 'v'
            if matrix == table:
                block_shape.append((x, y))
            else:
                blank_shape.append((x, y))
            dfs(x - 1, y, matrix)
            dfs(x + 1, y, matrix)
            dfs(x, y - 1, matrix)
            dfs(x, y + 1, matrix)
            return True
        return False

    # board 빈칸 추출
    blank_shape = []
    for i in range(length):
        for j in range(length):
            if game_board[i][j] == 0:
                dfs(i, j, game_board)
                blanks[len(blank_shape)].append(blank_shape[:])
                blank_shape.clear()
    # block 모양 추출
    block_shape = []
    for i in range(length):
        for j in range(length):
            if table[i][j] == 1:
                dfs(i, j, table)
                og = block_shape[:]
                flag = False
                for _ in range(4):
                    if flag:
                        break
                    for case in blanks[len(block_shape)]:
                        if check(sorted(og), sorted(case), len(block_shape)):
                            if case not in answer:
                                answer.append(case)
                                flag = True
                                break
                    og = rotate(og)
                block_shape.clear()
    result = 0
    for i in answer:
        result += len(i)
    return result

2. 후기

after_rotation[j][n - 1 - i] = before_rotation[i][j]

2차원 배열을 90도 회전시키는 코드는 기억하기 쉬우니 암기하도록 하자.

def rotate_90_degree(a):
    n = len(a)
    m = len(a[0])
    result = [[0]*n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            result[j][n-1-i] = a[i][j]
    return result
profile
안녕하세요!

0개의 댓글