[Python - Simulation, implementation] 18808 - 스티커 붙이기

📌 문제

혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연결되어 있다. 또한 모눈종이의 크기는 스티커의 크기에 꼭 맞아서, 상하좌우에 스티커가 포함되지 않는 불필요한 행이나 열이 존재하지 않는다.

아래는 올바른 모눈종이의 예시이다. 주황색 칸은 스티커가 붙은 칸을, 하얀색 칸은 스티커가 붙지 않은 칸을 나타낸다.

반면 아래는 올바르지 않은 모눈종이의 예시이다. 첫 번째는 윗쪽에 불필요한 행이 있고, 두 번째는 왼쪽에 불필요한 열이 있다. 그리고 세 번째는 스티커의 각 칸이 상하좌우로 모두 연결되어 있지 않다.

혜윤이는 자신의 노트북에 이 스티커들을 붙이기로 했다. 혜윤이의 노트북은 마침 직사각형 모양이고, 스티커가 인쇄된 모눈종이와 같은 간격으로 격자가 그려져 있다. 혜윤이는 스티커들을 먼저 받았던 것부터 차례대로 격자에 맞춰서 붙이려고 한다.

혜윤이가 스티커를 붙이는 방법은 다음과 같다.

 

1. 스티커를 회전시키지 않고 모눈종이에서 떼어낸다

2. 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.

3. 선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복한다.

4. 위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

 

아래의 예시를 통해 스티커를 붙이는 과정을 이해해보자. 노트북은 세로 5칸, 가로 4칸 크기이고, 혜윤이가 가지고 있는 스티커들은 아래와 같다. 왼쪽에서 오른쪽 순으로 스티커를 붙일 것이다.

1. 첫 번째 스티커는 회전 없이 온전히 붙일 수 있는 공간이 아래와 같이 6곳이 있다.

이 중에서 가장 위쪽의 위치, 가능한 가장 위쪽의 위치가 여러 개이면 그 중에서 가장 왼쪽의 위치는 첫 번째이다. 스티커를 붙인 후 노트북의 모양은 아래와 같다.

2. 두 번째 스티커는 회전 없이 온전히 붙일 수 있는 공간이 없다. 그러나 시계 방향으로 90도 회전한 후에는 붙일 수 있는 공간이 1개 생긴다. 해당 공간에 스티커를 붙인 후 노트북의 모양은 아래와 같다.

3. 세 번째 스티커는 스티커를 시계방향으로 0, 90, 180, 270도 회전시킨 모양에 대해 전부 확인을 해도 스티커를 붙일 수 있는 공간이 없다. 그러므로 해당 스티커를 붙이지 않고 버린다.

 

4. 네 번째 스티커는 스티커를 시계방향으로 0, 90, 180도 회전 시킨 모양에 대해 온전히 붙일 수 있는 공간이 없다. 그러나 시계 방향으로 270도 회전한 후에는 공간이 1개 생긴다. 스티커를 붙인 후 노트북의 모양은 아래와 같다. 최종적으로 노트북의 18칸이 스티커로 채워졌다.

혜윤이는 스티커를 다 붙인 후의 노트북의 모습이 궁금해졌다. 노트북의 크기와 스티커들이 주어졌을 때 스티커들을 차례대로 붙이고 난 후 노트북에서 몇 개의 칸이 채워졌는지 구해보자.

📌 입력

첫째 줄에 노트북의 세로와 가로 길이를 나타내는 N(1 ≤ N ≤ 40)과 M(1 ≤ M ≤ 40), 그리고 스티커의 개수 K(1 ≤ K ≤ 100)이 한 칸의 빈칸을 사이에 두고 주어진다.

 

그 다음 줄부터는 K개의 스티커들에 대한 정보가 주어진다. 각 스티커는 아래와 같은 형식으로 주어진다.

먼저 i번째 스티커가 인쇄된 모눈종이의 행의 개수와 열의 개수를 나타내는 R_i(1 ≤ R_i ≤ 10)와 C_i(1 ≤ C_i ≤ 10)가 한 칸의 빈칸을 사이에 두고 주어진다.

 

다음 R_i개의 줄에는 각 줄마다 모눈종이의 각 행을 나타내는 C_i개의 정수가 한 개의 빈칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1이다. 0은 스티커가 붙지 않은 칸을, 1은 스티커가 붙은 칸을 의미한다.

 

문제에서 설명한 것과 같이 스티커는 모두 올바른 모눈종이에 인쇄되어 있다. 구체적으로 스티커의 각 칸은 상하좌우로 모두 연결되어 있고, 모눈종이의 크기는 스티커의 크기에 꼭 맞아서 상하좌우에 스티커에 전혀 포함되지 않는 불필요한 행이나 열이 존재하지 않는다.

📌 출력

첫째 줄에 주어진 스티커들을 차례대로 붙였을 때 노트북에서 스티커가 붙은 칸의 수를 출력한다.

📌 문제 풀이

👨‍🏫 접근

이런 게 빡구현인가..? 하는 느낌이 드는 문제였다.

 

일단 문제를 봤을 때 고려해야 하는 기능은 세 가지가 있었다.

 

1. 스티커 회전 (2차원 리스트 회전)

스티커는 90도로 회전시킬 수 있다. 이때, 이러한 자료는 보통 2차원 리스트로 입력받아 사용하곤 하기 때문에 적절히 2차원 리스트를 회전시켜주어야 한다.

 

여기서 알아두면 좋은 것이 2차원 리스트 회전 방법이다. 예를 들어, 1~9까지 3행 3열인 벡터가 있다고 생각해보자. 그리고 이 리스트를 회전시키면 아래와 같다.

1 2 3		7 4 1
4 5 6	->	8 5 2
7 8 9		9 6 3

한 눈에 보면 위처럼 볼 수 있는데, 이를 2차원 리스트로 다시 표현하면 아래와 같다.

[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
👇🏻
[[7, 4, 1], [8, 5, 2], [9, 6, 3]]

유심히 보면 어느 정도 규칙성이 보인다. 일단 7은 2번 인덱스 리스트의 0번 인덱스 값이고, 4는 1번 인덱스 리스트의 0번 인덱스, 1은 0번 인덱스 리스트의 0번 인덱스 값이다.

 

즉, 0번 인덱스 리스트에는 각 인덱스 리스트의 0번 인덱스 값이 오게 되며, 역순으로 탐색하는 것이다. 이는 다른 인덱스 위치의 리스트도 마찬가지이다. '역순'은 단순히 거꾸로 읽어오면 되지만, 각각의 리스트에서 해당 인덱스 값을 가져오는 것은 어렵게 느껴질 수 있다. 하지만, 여기서 간단하게 zip함수와 *(애스터리스크)의 언패킹을 통해 해결할 수 있다.

⭐️ zip 함수, Unpacking

우리가 파일을 압축할 때 사용하는 확장자 중에 대표적으로 zip파일이 있다. 이와 유사하게 zip은 리스트 인자를 매개변수로 하여 각 리스트의 인덱스를 한꺼번에 묶어주는 기능을 한다. 예를 들어, 아래와 같이 장바구니 리스트들이 있다고 해보자.

cart1 = ['양파', '삼겹살', '콜라']
cart2 = ['당근', '항정살', '사이다']
cart3 = ['고추', '목살', '환타']

여기서 각 리스트의 인덱스 위치에는 채소, 고기, 음료가 들어있다. 이를 편하게 보고 싶으니 아래와 같이 처리한다고 하면, 꽤나 복잡해 보일 것이다.

subject = [[], [], []]

for cart in [cart1, cart2, cart3]:
	subject[0].append(cart[0])
    subject[1].append(cart[1])
    subject[2].append(cart[2])

여기서 zip함수를 통해서 반복문을 만들면 아래와 같다.

subject = []

for cart in zip(cart1, cart2, cart3):
	subject.append(cart)

물론 위의 예제가 상당히 단순하게 작성한 것이지만, 그래도 많이 단순해진 것을 볼 수 있다. 그리고, zip은 각 인덱스 요소를 튜플로 묶어주기 때문에 리스트나 기타 다른 자료형으로 만들고 싶다면, list나 set 등의 함수를 사용하도록 하면 된다.

그 다음 *(애스터리스크)는 여러 가지 역할을 하지만, 그중에서 컨테이너 요소에 사용할 때 리스트를 언패킹 해주는 역할을 한다. 실제로 print 함수를 통해 리스트의 요소들을 하나씩 공백을 두며 출력하고자 할 때, 종종 사용한다. 이때, zip함수와 사용하면 둘의 시너지가 발휘된다. 위에서 zip에 인자를 각각 집어넣어주었는데 이렇게 하지 않고 단순하게 언패킹을 사용해 인자에 집어넣어주면 쉽게 요소들을 압축시킬 수 있다.

carts = [cart1, cart2, cart3]
subject = []

for cart in zip(*carts):
	subject.append(cart)

def rotate(arr):
	return [list(element) for zip(*arr[::-1])]

처음 보면 어려워 보일 수 있는데 실상은 간단하다. 일단 역순으로 받기 위해서 배열의 순서를 역으로 바꿔주고, 각 인덱스 값을 받기 위해서 배열을 언패킹 해주며 zip으로 각 인덱스 값을 묶어준다.

 

풀어서 보자면 아래와 같이 볼 수 있다.

arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

for i in zip(*arr[::-1]):
	print(i)				# (7, 4, 1) \n (8, 5, 2) \n (9, 6, 3)
    
for i in zip([7, 8, 9], [4, 5, 6], [1, 2, 3]):
	print(i)				# (7, 4, 1) \n (8, 5, 2) \n (9, 6, 3)

이런 방식으로 2차원 리스트를 배열할 수 있다. 행과 열의 개수가 달라도 가능하다.

 

2. 위치 바꿔가며 스티커 붙이기

본문 1번에서 H모양의 스티커를 위치를 바꿔가며 붙이고 있다. 총 6번 위치를 바꿔가며 스티커를 붙일 수 있는지 체크한다.

 

먼저 열 방향으로 이동을 한 후에 행 방향으로 한 번 이동한 후 동일한 프로세스를 반복한다. 그렇기 때문에 for문을 2중으로 두어서 노트북 공간의 일부분을 검사하도록 해야 한다. 이 과정을 수행하기 위해서 함수를 구성했다.

def put(sticker):
    sr, sc = len(sticker), len(sticker[0])

    for x in range(n - sr + 1):
        for y in range(m - sc + 1):
            if compare(x, y, sr, sc, sticker):
                for sx in range(sr):
                    for sy in range(sc):
                        laptop[x + sx][y + sy] += sticker[sx][sy]
                return True

    return False

sticker의 행과 열의 개수를 받아서 저장해주고, 노트북의 세로 가로 크기에 연산을 하여 이동할 수 있는 횟수만큼 반복해주었다. 여기서 compare함수는 가능/불가능을 체크해주는 함수이고, 모든 탐색에서 불가능하다면 False를 반환하고, 중간에 가능하다면 True를 반환한다. 그리고 붙일 수 있기 때문에 바로 laptop 2차원 리스트에 해당 내용을 기록해준다.

 

3. 현재 노트북 섹션과 스티커 비교

노트북에 스티커를 붙이기 위해서는 붙일 곳과 스티커의 범위가 같아야 하며, 해당 섹션에 스티커가 겹치지 않아야 한다. 이를 검사하는 방법을 단순하다. 이미 범위는 고려해서 함수를 작성했기 때문에, 스티커가 겹치지 않는지만 확인하면 된다. 스티커가 겹치는 것은 해당 섹션의 좌표에 이미 스티커가 붙어 있는 경우이다. 그렇기 때문에 2중 for문으로 반복하면서 값이 같으며, 그 값이 1인 경우만 체크해주면 된다.

 

def compare(x, y, sr, sc, sticker):
    for sx in range(sr):
        for sy in range(sc):
            if laptop[x + sx][y + sy] == sticker[sx][sy] == 1:
                return False

    return True

 

이제 이 3가지 기능을 사용하면 충분히 문제를 풀이할 수 있을 것이다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
input = sys.stdin.readline


def rotate(s):
    s = zip(*s[::-1])
    return [list(e) for e in s]


def put(sticker):
    sr, sc = len(sticker), len(sticker[0])

    for x in range(n - sr + 1):
        for y in range(m - sc + 1):
            if compare(x, y, sr, sc, sticker):
                for sx in range(sr):
                    for sy in range(sc):
                        laptop[x + sx][y + sy] += sticker[sx][sy]
                return True

    return False


def compare(x, y, sr, sc, sticker):
    for sx in range(sr):
        for sy in range(sc):
            if laptop[x + sx][y + sy] == sticker[sx][sy] == 1:
                return False

    return True


n, m, k = map(int, input().split())

laptop = [[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 i in range(4):
        if put(sticker):
            break
        sticker = rotate(sticker)

cnt = sum(map(sum, laptop))

print(cnt)

📄 준비

import sys
input = sys.stdin.readline


def rotate(s):
    s = zip(*s[::-1])
    return [list(e) for e in s]

...

n, m, k = map(int, input().split())

laptop = [[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)

...

일단 회전 함수를 미리 준비해주고, 스티커를 붙일 노트북 및 스티커 리스트를 준비해준다.

📄 풀이

def put(sticker):
    sr, sc = len(sticker), len(sticker[0])

    for x in range(n - sr + 1):
        for y in range(m - sc + 1):
            if compare(x, y, sr, sc, sticker):
                for sx in range(sr):
                    for sy in range(sc):
                        laptop[x + sx][y + sy] += sticker[sx][sy]
                return True

    return False

def compare(x, y, sr, sc, sticker):
    for sx in range(sr):
        for sy in range(sc):
            if laptop[x + sx][y + sy] == sticker[sx][sy] == 1:
                return False

    return True
    
for sticker in stickers:
    for i in range(4):
        if put(sticker):
            break
        sticker = rotate(sticker)

cnt = sum(map(sum, laptop))

print(cnt)

각 스티커들을 모두 순회해준다. 이때 90도 방향으로 네 번 회전시킬 수 있으므로 해당 스티커를 방향에 따라 4번 조회해준다. 만약 붙일 수 있다면 바로 break해주고, 그렇지 않다면 회전하여 다시 시도해준다.

 

모두 마친 후에는 각 리스트의 1값을 모두 더해서 정답을 출력해준다.

📌 총평

구현해야 할 것들이 좀 많아서 곤란했다.

 

여기서는 함수를 많이 만들어 두어야 했다. return하면서 반복문을 아예 벗어나야 하는데 그렇지 못해서 함수의 return을 사용해야 했고, 각 함수의 역할을 확실히 하기 위해서 다른 내용은 다른 함수로 구현하는 것이 좋았다.

 

적은 횟수로 도전해 성공하여 뿌듯했지만, 구현력이 아직은 부족하다. 시간이 오래 걸렸기 때문이다. 이 부분은 열심히 보완해야 할 것이다.