[BOJ/백준] 18808 스티커 붙이기 파이썬

문제 링크 : https://www.acmicpc.net/problem/18808

18808번: 스티커 붙이기

 

주어진 스티커를 순서대로 붙이는데 회전이 가능하다.

이때 스티커가 겹치거나 범위를 벗어나면 안되야하고 회전했는데도 못붙이는 경우에는 해당 스티커는 버린다.

 

스티커 회전의 경우 Maaaaaaaaaze 풀면서 썼던 방식과 비슷한데 다른 점이 하나 있다.

Maaaaaaaaaze의 경우 회전해도 배열의 크기가 같지만 이번 문제는 회전하면 가로, 세로 길이가 서로 바뀐다.

그래서 바뀐 길이만큼 tmp를 생성했다.

 

다음 스티커를 붙이는 경우이다.

for문으로 돌려서 체크 했다.

스티커의 크기가 3x4이고 board의 크기가 5x5라면 스티커의 가장 왼쪽 끝 칸은 2x1칸 안에서만 확인하면 된다. 그 외의 칸의 경우 board를 벗어나게 되므로 안봐도 된다.

 

범위를 체크 했으니 이제 붙이는 과정이다.

붙이려는 칸에 값이 0이거나 스티커의 첫번째 칸의 값이 0인 경우 해당 칸부터 체크를 시작한다.

해당 칸에서 시작해서 스티커의 크기 만큼 돌면서 스티커의 값이 1이고 board의 값이 0 인 경우 board에 값을 1로 바꾸로 개수를 셌다. 스티커를 해당 시작점에서 붙일 수 있다면 개수를 리턴해준다.

 

그렇지 않은 경우 시작점에서 스티커를 붙일 수 없는 경우이다. 이때는 다시 이전 상태로 돌려놔야한다.

이때 시작점에서 다시 스티커 크기 만큼 도는데 위에서 구한 개수 만큼 돌면서 스티커의 값이 1인 경우 해당 칸은 0으로 바꿔야 하는 칸이니 0으로 바꾼다.

위에서 구한 개수는 1로 바꾼 개수이므로 그 개수 다음부터는 확인하지 않은 경우이니 볼 필요가 없다.

 

from sys import stdin

input = stdin.readline

n,m,k = map(int, input().split())
board = [[0]*m for _ in range(n)]

blocks = []

for _ in range(k):
    r,c = map(int, input().split())
    block = [list(map(int, input().split())) for _ in range(r)]
    blocks.append(block)
def solv():
    answer = 0
    for block in blocks:
        for _ in range(4):
            cnt = insert_block(block)
            if cnt != 0:
                answer += cnt
                break
            block = rotate_block(block)
    print(answer)
def insert_block(block):
    global board

    r,c = len(block),len(block[0])
    for sx in range(n-r+1):
        for sy in range(m-c+1):
            if board[sx][sy] == 0 or block[0][0] == 0:
                cnt = 0
                flag = False
                for x in range(r):
                    for y in range(c):
                        if block[x][y] == 1:
                           if board[sx+x][sy+y] == 0:
                               cnt += 1
                               board[sx+x][sy+y] = 1
                           else:
                               flag = True
                               break
                    if flag:
                        break
                if flag:
                    rollback_board(cnt, sx, sy, r, c, block)
                else:
                    return cnt
    return 0
def rollback_board(cnt,sx,sy,r,c,block):
    global board

    tmp = 0
    if tmp == cnt:
        return

    for x in range(r):
        for y in range(c):
            if block[x][y] == 1:
                board[sx+x][sy+y] = 0
                tmp += 1

                if tmp == cnt:
                    return
def rotate_block(block):
    r,c = len(block),len(block[0])
    tmp = [[0]*r for _ in range(c)]

    for x in range(r):
        for y in range(c):
            tmp[y][r-x-1] = block[x][y]
    return tmp

solv()