[알고리즘] 백준 - 스티커 붙이기

백준 - 스티커 붙이기

내 풀이

import sys
sys.setrecursionlimit(100000)

def count_cell(empty_paper):
    count = 0
    for i in range(len(empty_paper)):
        for j in range(len(empty_paper[0])):
            if empty_paper[i][j] == 1:
                count += 1
    return count

def paste_sticker(rotated_sticker, empty_paper, y, x):
    for i in range(len(rotated_sticker)):
        for j in range(len(rotated_sticker[0])):
            if rotated_sticker[i][j] != 0:
                empty_paper[i+y][j+x] = 1

def sticker_fit(rotated_sticker, empty_paper, y, x):
    for i in range(len(rotated_sticker)):
        for j in range(len(rotated_sticker[0])):
            if i + y < 0 or i + y >= len(empty_paper) or j + x < 0 or j + x >= len(empty_paper[0]):
                return False
            if rotated_sticker[i][j] != 0 and empty_paper[i+y][j+x] != 0:
                return False
    return True

def rotate_90(m):
    return [k[::-1] for k in zip(*m)]

def get_rotated_stickers(sticker):
    return_list = []
    return_list.append(sticker[:])
    for _ in range(3):
        sticker = rotate_90(sticker)
        return_list.append(sticker)

    return return_list

def print_board(board):
    print()
    for i in range(len(board)):
        for j in range(len(board[0])):
            print(board[i][j], end = " ")
        print()
    print()

N, M, K = map(int, input().split())

empty_paper = [[0] * M for _ in range(N)]

stickers = []

for _ in range(K):
    r, c = map(int, input().split())
    sticker = [list(map(int, input().split())) for _ in range(r)]
    stickers.append(sticker)

for sticker in stickers:
    pasted = False

    rotated_stickers = get_rotated_stickers(sticker)
    for rotated_sticker in rotated_stickers:
        for i in range(len(empty_paper)):
            for j in range(len(empty_paper[0])):
                if sticker_fit(rotated_sticker, empty_paper, i, j):
                    paste_sticker(rotated_sticker, empty_paper, i, j)
                    pasted = True
                    break
            if pasted:
                break
        if pasted:
            break

print(count_cell(empty_paper))

단순 구현이었기 때문에 다른 부분에서 특별히 어려운 것은 없었으나, 2차원 배열 90도 회전하는 쉬운 방법들에 대해 찾아보았고 알게 되었다.

이전 같았으면 맨 바깥의 한 줄씩 저장해서 다시 깔아주는 방식으로 회전을 구현했을 것이다. 하지만 그것보다 훨씬 쉬운 방식 두 가지가 있다.

2차원 배열 90도 회전 시키는 방법