[백준/Python]18808: 스티커 붙이기

문제

https://www.acmicpc.net/problem/18808
백준 문제집 - 0x0D강 - 시뮬레이션

 

알고리즘: 브루트포스, 시뮬레이션

---

풀이

주어진 스티커들을 조건에 맞게 붙여나가는 문제다.

1. 겹쳐서 붙이지 말것.
2. 왼쪽 상단, 오른쪽 상단, 왼쪽 하단, 오른쪽 하단 순으로 우선순위를 두고 붙일것.
3. 붙일 수 없는 상황이라면 스티커를 90도씩 회전시켜본 후 다시 시도

잘 보면 '최대한 많이 붙일수있는 경우'를 구하는게 아니다.
단순히 1번 스티커부터 K번 스티커까지 붙일 수 있는 경우에만 붙여나가면 된다.

 

먼저 각 스티커들을 리스트에 저장한 뒤 하나씩 순회한다.
스티커를 0º(기본), 90º, 180º, 270º 씩 돌려가며 방향 우선순위에 맞춰 노트북에 붙일 수 있는지 체크한다.
붙일 수 있다면 붙인 후 바로 다음 스티커로 넘어간다.

 

그럼 스티커를 회전시킬 함수, 붙일 수 있는지 체크하는 함수, 실제로 붙이는 함수가 필요하다.

 

회전함수는 생각보다 간단하다.
R x C 크기의 리스트 arr이 있고, 이걸 90º 회전시킨 리스트를 rotated라고 가정해보자.
rotated는 C x R 크기의 리스트가 될 것이다.
그리고 각각의 위치값을 계산해보면, rotated[j][R-1-i] = arr[i][j]가 된다.

111
000

01
01
01

 

체크함수에서는 먼저 현재 좌표(x, y)에서 스티커의 크기만큼 더한 값이 R, C보다 큰 경우 바로 False를 반환해준다.
그리고 반복문을 통해 스티커의 각 좌표를 확인한다.
해당 좌표에 이미 다른 스티커가 존재한다면 바로 False, 좌표를 다 검사할때까지 걸리지 않는다면 True를 반환한다.

 

전체 코드

# 메모리: 31120KB / 시간: 228ms
from sys import stdin


input = stdin.readline

def rotate(sticker):
    R, C = len(sticker), len(sticker[0])
    rotated = [[0] * R for _ in range(C)]

    for i in range(R):
        for j in range(C):
            rotated[j][R-1-i] = sticker[i][j]
    return rotated

def checking(sticker, x, y):
    R, C = len(sticker), len(sticker[0])

    if x + R > N or y + C > M:
        return False

    for i in range(R):
        for j in range(C):
            if sticker[i][j] == 1:
                if board[x+i][y+j] == 1:
                    return False
    return True

def placing(sticker, x, y):
    R, C = len(sticker), len(sticker[0])

    for i in range(R):
        for j in range(C):
            if sticker[i][j] == 1:
                board[x+i][y+j] = 1

N, M, K = map(int, input().split())
board = [[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:
    for _ in range(4):
        placed = False
        for i in range(N):
            for j in range(M):
                if checking(sticker, i, j):
                    placing(sticker, i, j)
                    placed = True
                    break  # j 빠져나옴
            if placed:
                break  # i 빠져나옴
        if placed:
            break  # 방향 for문 빠져나옴
        sticker = rotate(sticker)

ret = sum(sum(line) for line in board)
print(ret)