문제

BOJ 18808: 스티커 붙이기 https://www.acmicpc.net/problem/18808

풀이

조건

• 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.
• 스티커를 회전시키지 않고 노트북에 대본다.
• 스티커를 붙일 수 있다면 붙인다.
• 스티커를 붙일 수 있는 부분이 없다면 90도씩 돌려서 다시 대본다.
• 360도 돌려봐도 붙일 공간이 없다면 해당 스티커는 버린다.
• 스티커는 입력 받은 순서대로 붙인다.

풀이 순서

• 입력받은 스티커를 노트북에 붙일 수 있는지 확인한다.
  • 노트북 모든 공간을 체크해 스티커를 붙일 수 있는지 확인한다.
• 스티커를 붙일 수 있다면 스티커가 붙는 노트북의 위치에 '1'을 기록한다.
• 붙일 공간이 없다면 90도 돌려서 다시 확인해본다.
• 360도 모두 확인해봤는데도 붙일 공간이 없다면 해당 스티커는 버린다.
• 모든 스티커를 확인해 본 뒤 스티커가 붙어있는 공간의 넓이를 구한다.

코드

Python

import sys
from collections import deque


# 스티커를 시계 방향으로 90도 회전시키는 함수
def rotate(original):
    # 회전 시키면 가로, 세로 높이가 바뀌기 때문에 새로 구해줌
    new_r = len(original[0])
    new_c = len(original)
    new_sticker = [[0 for _ in range(new_c)] for _ in range(new_r)]

    que = deque()
    for i in range(len(original)):
        for j in range(len(original[0])):
            que.append(original[i][j])

    # 90도 돌림
    for j in range(new_c - 1, -1, -1):
        for i in range(new_r):
            new_sticker[i][j] = que.popleft()

    return new_sticker


# 해당 위치에 현재 스티커를 붙일 수 있는지 확인하는 함수
def can_put_sticker_on_board(r_start, c_start, now_sticker):
    global board
    stick_row_idx = 0
    for r in range(r_start, r_start + len(now_sticker)):
        stick_col_idx = 0
        for c in range(c_start, c_start + len(now_sticker[0])):
            # 범위 체크
            if r < 0 or c < 0 or r >= N or c >= M:
                return False
            # 스티커를 붙일 수 없는 자리인지 체크
            if now_sticker[stick_row_idx][stick_col_idx] == 1 and board[r][c] == 1:
                return False
            stick_col_idx += 1
        stick_row_idx += 1

    return True


# 스티커를 붙일 노트북의 위치를 탐색하는 함수
def find_position(now_sticker):
    global board
    for r_start in range(N):
        for c_start in range(M):
            result = can_put_sticker_on_board(r_start, c_start, now_sticker)
            # 스티커 붙일 수 있는 자리면 해당 시작 위치 반환
            if result:
                return True, r_start, c_start

    return False, -1, -1


N, M, K = map(int, sys.stdin.readline().rstrip().split())

# 노트북 상태
board = [[0 for _ in range(M)] for _ in range(N)]

# 스티커를 순서대로 받으면서 붙일 수 있는 곳에 붙임
# 0 -> 빈 칸 // 1 -> 스티커 붙은 칸
for p in range(1, K + 1):
    # 스티커 크기 입력 받음
    R, C = map(int, sys.stdin.readline().rstrip().split())
    # 스티커 모양 입력 받기
    sticker = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(R)]

    # 스티커 붙여봄 (현재 모양으로 안되면 90도씩 회전)
    for _ in range(4):
        # 노트북에 붙일 자리가 있는지 확인
        can_stick = find_position(sticker)

        # 스티커 붙일 수 있으면
        if can_stick[0]:
            stick_r_idx = 0
            for i in range(can_stick[1], can_stick[1] + len(sticker)):
                stick_c_idx = 0
                for j in range(can_stick[2], can_stick[2] + len(sticker[0])):
                    # 스티커 모양대로 노트북에 붙임('1' 기록되게 함)
                    if sticker[stick_r_idx][stick_c_idx] == 1:
                        board[i][j] = sticker[stick_r_idx][stick_c_idx]
                    stick_c_idx += 1
                stick_r_idx += 1
            break
        # 안되면 회전 시킴
        else:
            sticker = rotate(sticker)

answer = 0
for i in range(N):
    for j in range(M):
        if board[i][j] == 1:
            answer += 1

print(answer)

정리

• 코드가 돌아가는 중간 중간에 갱신된 상태를 출력해보며 디버깅 해보는 점의 중요성을 크게 느꼈다.