[Python / BOJ 18808] 스티커 붙이기

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

18808번: 스티커 붙이기

 

0. 문제

 

아래 규칙으로 노트북에 스티커를 붙인다.

 

1. 스티커를 회전시키지 않고 모눈종이에서 떼어낸다.
2. 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 붙일 수 있는 위치가 여러 개라면 가장 위, 그 중에서도 가장 왼쪽 위치에 붙인다.
3. 선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복한다.
4. 위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

 

다음과 같은 스티커가 있으면 차례로 다음처럼 붙인다.

 

 

 

 

 

 

 

1. 아이디어

1. 시뮬레이션은 레벨이 높아질수록 함수로 빼는 게 중요한 것 같다.
   • 기본적으로 회전, 스티커 붙이는 함수로 나누려고 했다.
   • 작성하다 보니 회전, 스티커 붙일 위치 찾는 함수, 붙일 수 있는지 확인하는 함수, 붙이는 함수로 나뉘었다.
2. 90도 회전시키기
   • 회전시키는 것은 예전에 많이 해봤어서 익숙한 코드를 그대로 썼다.
   • ans = [i[::-1] for i in zip(*matrix)]

     
     arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]]
     
     # 전치행렬
     arr_trans = [list(i) for i in zip(*arr)]
     
     # 시계 방향으로 90도 회전
     arr_cw90_tuple = list(zip(*arr[::-1]))
     # arr_cw90_list1 = list(map(list, zip(*arr[::-1])))
     arr_cw90_list2 = [list(i) for i in zip(*arr[::-1])]
     
     # 반시계 방향으로 90도 회전
     arr_ccw90_tuple = list(zip(*arr))[::-1]
     # arr_ccw90_list1 = list(map(list, list(zip(*arr))[::-1]))
     arr_ccw90_list2 = [list(i) for i in list(zip(*arr))[::-1]]

3. 스티커 붙이기
   • 스티커 붙일 위치 찾기
     
     • dr, dc로 노트북 영역을 움직여서 스티커 영역과 비교하도록 한다.
     • 스티커를 붙일 수 있는지 확인한다.
     • 스티커를 붙일 수 있으면 스티커를 붙인다.
   • 스티커 붙일 수 있는지 확인하기
     
     • 노트북과 스티커의 각 좌표의 값을 비교한다.
     • 스티커의 값이 1인데 노트북 값도 1이면 스티커를 붙일 수 없다.
   • 스티커 붙이기
     • 노트북과 스티커의 각 좌표의 값을 비교한다. 
     • 스티커의 값이 1이면 노트북에 1을 쓰고, 0이면 넘어간다.

 

 

 

2. 전체 코드

 

# 90도 회전
def rotate90(matrix: list) -> list:
    ans = [i[::-1] for i in zip(*matrix)]
    return ans


# 스티커 붙일 수 있는 위치인지 체크
def can_sticker(dr, dc):
    for r in range(R):
        for c in range(C):
            # 범위 넘어가면 못 붙임
            if not (0 <= r + dr < N and 0 <= c + dc < M):
                return 0
            # 노트북이랑 스티커가 겹치면 붙일 수 없음
            if notebook[r + dr][c + dc] and sticker[r][c]:
                return 0
    # 모든 곳이 겹치지 않으면 붙일 수 있음
    return 1


# 스티커 붙이기
def put_sticker(dr, dc):
    for r in range(R):
        for c in range(C):
            if sticker[r][c]:
                notebook[r + dr][c + dc] = 1
    return 1


# 스티커 붙일 자리 찾기
def find_sticker_position_and_put():
    # flag : 스티커 붙였는지
    flag = 0
    for dr in range(N - R + 1):
        for dc in range(M - C + 1):
            # 만약 스티커 붙일 수 있으면 스티커 붙이고 끝내기
            if can_sticker(dr, dc):
                flag = put_sticker(dr, dc)
                return flag
    return flag


N, M, K = map(int, input().split())
notebook = [[0] * M for _ in range(N)]

for _ in range(K):
    R, C = map(int, input().split())
    sticker = [list(map(int, input().split())) for _ in range(R)]

    # 4방향 회전하면서 위치 찾기
    for rotate_num in range(4):
        flag = find_sticker_position_and_put()
        # 스티커 붙일 수 있는 자리 찾고 붙였으면 끝
        if flag:
            break
        # 못찾았으면 회전하고 R, C 바꾸기
        else:
            sticker = rotate90(sticker)
            R, C = C, R

# 스티커가 붙은 칸의 수 출력
ans = 0
for i in range(N):
    ans += sum(notebook[i])
print(ans)