[백준 Python] 18808 스티커 붙이기 - 구현

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

18808번: 스티커 붙이기

 

 

문제는 주어진 좌표공간에 서로 다른 크기의 N*N 사이즈의 스티커를 잘 회전시켜 붙이는 문제다. 원하는 곳에 넣을 수 있는 테트리스라고 생각하면 된다. 각 스티커는 순서가 정해져 있고 회전 또한 시계 방향으로 90도씩 회전하여 붙일 수 있는지 판별한다.

스티커 예시

가로가 4칸 세로가 5칸인 구역에 위의 4개의 스티커를 붙일것이다. 왼쪽 위부터 붙여나가므로 1번은 그대로 붙는다. 2번은 회전하여 붙고 3번은 자리가 없어서 붙이지 않고 버린다. 최종 모습은 아래와 같다.

4*5 최종 모습

전체 노트북이 최대 40X40 크기이고 각 스티커는 10X10이 최대 크기다. 스티커 개수는 최대 100개이다.

따라서 최악의 경우 16개가 먼저 붙고 뒤의 84개가 붙을 수 있는지 판별해야한다. 84 * 4 * 300(판별 구역의 가장 왼쪽 위 개수) * 100(판별 구역의 크기) =  10,080,000 1천8만이지만, 판별 구역의 크기는 만약 스티커가 붙어있다면 return 해서 빠져나오고 판별 구역의 개수 또한 이미 스티커가 붙은 곳은 시작점에서 제외된다. 이미 앞에서 붙은 스티커가 있으므로 판별 구역의 개수는 300보다 작고 판별 구역의 크기 또한 각 스티커에 비어있는 행과 열은 있을 수 없으므로 크기도 10보다 작아진다. 따라서 반복문으로 해결해도 중간에 return으로 빠져나오면 시간 안에 해결 가능하다.

 

스티커의 회전을 구현해야하는데, 시계방향으로 90도 회전한 모습을 새로운 배열에 복사하여 넣고 새로운 배열을 반환했다. 원래 스티커에서 x값과 t값이 바뀌는데 맨 왼쪽 아래가 (0,0) 이 되는 것을 고려해서 새로운 배열에 복사한다.

check 함수를 만들어서 만약 스티커를 붙일 수 있다면 전체 graph에 붙인다.

 

import sys

def transX(x,y,g):
    new_g = [[0 for i in range(x)] for i in range(y)]

    for i in range(y):
        for j in range(x):
            new_g[i][j] = g[x-j-1][i]

    return new_g

def check(x,y,g):
    l = len(g)
    k = len(g[0])
    for i in range(l):
        for j in range(k):
            if(g[i][j] == 1 and graph[x+i][y+j] == 1):
                return 0
    for i in range(l):
        for j in range(k):
            if(g[i][j]==1):
                graph[x+i][y+j] = g[i][j]
    return 1

n,m,k = map(int,sys.stdin.readline().split())

st = []
graph = [[0 for _ in range(m)] for _ in range(n)]

for i in range(k):
    x,y = map(int,sys.stdin.readline().split())
    g = [list(map(int,sys.stdin.readline().split())) for _ in range(x)]
    st.append([(x,y),g])
for w in st:
    hasSticked = False
    for I in range(4):
        x,y = w[0]
        g = w[1]
        for i in range(n-x+1):
            if(hasSticked):
                break
            for j in range(m-y+1):
                if(check(i,j,g)): 
                    hasSticked = True
                    break
        if(hasSticked):break
        w[1] = transX(x,y,g)
        w[0] = (y,x)
res =0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1: res += 1
print(res)