[백준] 18808번 스티커 붙이기 - 파이썬(Python)

문제 (링크)

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

18808번: 스티커 붙이기

 

나의 풀이

import sys
input = sys.stdin.readline

# 스티커 90도 회전
def rotate_by_90(sticker_board):
    r, c = len(sticker_board), len(sticker_board[0])
    rotated_sticker_board = [[0] * r for _ in range(c)]
    for i in range(c):
        for j in range(r):
            rotated_sticker_board[i][j] = sticker_board[r-j-1][i]
    
    return rotated_sticker_board

# 현재 위치에 붙일 수 있는지 없는지 확인
def is_attachable(x, y, sticker_board):
    r, c = len(sticker_board), len(sticker_board[0])
    for i in range(r):
        for j in range(c):
            if sticker_board[i][j] == 1 and notebook[x+i][y+j] == 1:
                return False
    
    return True

# 현재 위치에 스티커 붙임
def attach(x, y, sticker_board):
    r, c = len(sticker_board), len(sticker_board[0])

    for i in range(r):
        for j in range(c):
            if sticker_board[i][j] == 1:
                notebook[x+i][y+j] = 1


if __name__ == '__main__':
    n, m, k = map(int, input().split())
    notebook = [[0] * m for _ in range(n)]
    stickers = [{} for _ in range(n)]
	
    # 스티커 정보는 딕셔너리로 관리
    for i in range(k):
        r, c = map(int, input().split())
        stickers[i]['r'], stickers[i]['c'] = r, c
        stickers[i]['sticker_board'] = [list(map(int, input().split())) for _ in range(r)]

    for i in range(k):
        s_n, s_m = stickers[i]['r'], stickers[i]['c']
        current_sticker = stickers[i]['sticker_board']
        rotation_cnt = 0

        while rotation_cnt < 4:
        	# 현재 스티커의 크기가 노트북 범위를 벗어나면 회전
            if s_n > n or s_m > m:
                s_n, s_m, current_sticker = s_m, s_n, rotate_by_90(current_sticker)

                continue
            
            # 벗어나지 않는다면 붙일 수 있는지 확인
            is_attached = False
            
            for i in range(n - s_n + 1):
                for j in range(m - s_m + 1):
                    if is_attachable(i, j, current_sticker):
                        attach(i, j, current_sticker)
                        is_attached = True
                        break
                
                # 두 번째 for문 break
                if is_attached:
                    break
                    
            # while문 break
            if is_attached:
                break
            
            else:
                s_n, s_m, current_sticker = s_m, s_n, rotate_by_90(current_sticker)
                rotation_cnt += 1

    ans = 0
    for i in range(n):
        for j in range(m):
            if notebook[i][j] == 1:
                ans += 1

    print(ans)

코드 설명 및 풀이

로직 자체는 간단하지만 구현에 있어서 생각보다 까다롭고 시간도 많이 걸리는 문제이다.

 

우선, 스티커를 90도로 돌리는 것부터 처음해봐서 꽤 애를 먹었지만 막상 하고 나니깐 별 거 아니긴 했다.

 

스티커를 순서대로 가지고 와서 notebook에 삽입할 수 있으면 삽입해주고, 해당 자리는 스티커가 붙여졌다는 의미로 notebook의 배열의 값을 1로 업데이트 해준다.

 

삽입할 수 없다면 최대 4번까지 회전해가면서 동일한 작업을 반복해주면 된다.