[python] 백준 18808 스티커 붙이기

https://www.acmicpc.net/problem/18808

18808번: 스티커 붙이기

 

문제 해결

• 스티커를 붙이는 방법이 상세하게 나왔다. 최대한 있는 그대로 붙이려 하되, 안되면 90 오른쪽으로 회전해가며 붙여보고 그래도 안붙여지면 버리고 다른 것을 순서대로 붙이는 것이다.
• 따라서 우리는 붙일 수 있는지 확인하고 붙여질 수 있으면 붙이고 옮겨가며 붙여보되, 안되면 회전을 시키고 반복하는 알고리즘을 짜면 된다.

 

CODE

import copy

def checking(r:int,c:int,i:int,j:int):
    global stick
    for y in range(r):
        for x in range(c):
            if board[i+y][j+x] + stick[y][x] > 1:
                return False
    return True

def attach(r:int,c:int,i:int,j:int):
    global stick
    for y in range(r):
        for x in range(c):
            board[i+y][j+x] += stick[y][x]
    return

def rotate(r:int,c:int):
    global stick
    result = [[0 for _ in range(r)] for _ in range(c)]
    # print(f"rotate 안에서 stick 행:{len(stick)} stick 열:{len(stick[0])}")
    for i in range(r):
        for j in range(c):
            result[j][r-i-1] = stick[i][j]    
    return result

def solve(n,m,r,c):
    global stick
    check = False
    cnt = 0
    while cnt<4:
        if check:break
        for i in range(n-r+1):
            if check:break
            for j in range(m-c+1):
                if checking(r,c,i,j):
                    attach(r,c,i,j)
                    check = True
                    break
        else:
            # print(f"stick 행:{r} stick 열:{c}")
            stick = rotate(r,c)
            r, c = c, r
            # print(f"stick 행:{r} stick 열:{c}")
            cnt += 1
        

if __name__=='__main__':
    n, m, k = map(int, input().split())
    board = [[0 for _ in range(m)] for _ in range(n)]
    for _ in range(k):
        r, c = map(int, input().split())
        stick = []
        for _ in range(r):
            stick.append(list(map(int,input().split())))
        solve(n,m,r,c)
    answer = 0
    for i in range(n):
        for j in range(m):
            answer += board[i][j]
    print(answer)