백준 테트로미노

🔗 프로그래머스 퍼즐 조각 채우기 문제와 비슷

퍼즐 조각 채우기 문제에서도 배열의 회전과 도형 문제여서 비슷하다고 생각

배열의 회전(왼쪽으로 90도씩 회전)

1 1 0     0 1    1 1 0     0 1                 
0 1 1 ⬅️  1 1 ⬅️ 0 1 1 ⬅️  1 1  
          1 0              1 0                 
map_3    map_2   map_1     map

map = [[0, 1], [1, 1], [1, 1]]
print(map) # [[0, 1], [1, 1], [1, 0]]
map_1 = [list(x) for x in zip(*map)][::-1]
print(map_1) # [[1, 1, 0], [0, 1, 1]]
map_2 = [list(x) for x in zip(*map_1)][::-1]
print(map_2) # [[0, 1], [1, 1], [1, 0]]
map_3 = [list(x) for x in zip(*map_2)][::-1]
print(map_3) # [[1, 1, 0], [0, 1, 1]]

python

💡

* → packing, unpacking 연산자

unpacking
리스트, 튜플 등 시퀀스 자료형 앞에 * 를 붙이면 해당 시퀀스의 값을 하나씩 풀어서(=언패킹) 함수의 인자 등으로 전달
```
def temp(a, b, c):
	pass

nums = [1, 2, 3]
temp(*nums) # temp(1, 2, 3)과 동일하게 동작
```
python

packing
함수 정의에서 매개변수 앞에 * 를 붙이면 여러 개의 인자를 하나의 튜플로 묶어줌
```
def temp(*args):
	print(args)

temp(1, 2, 3) # (1, 2, 3) 출력
```
python

💡

2차원 배열 회전에서의 사용

zip(*arr) 처럼 사용하면, 2차원 배열의 각 행을 풀어서 zip 에 전달하고, 전치(transpose) 연산을 쉽게 할 수 있음

arr = [[1, 2], [3, 4]]
list(zip(*arr)) # [(1, 3), (2, 4)]

python

전치 후 거꾸로 바꿔야 90도 회전

1 2  
3 4

1 3 
2 4

2 4 
1 3

정사각형 4개를 이어 붙인 폴리오미노 = 테트로미노

문제가 헷갈렸다. 원래 있는 테트로미노에 한 번만 대칭을 해도 된다는 건지, 회전한 후에 대칭시켜도 된다는 건지. 결국에는 회전한 후에 대칭시켜도 되는 거였다.

“테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.”

import sys

def rotate(shape):
    """90도 회전"""
    return [list(row) for row in zip(*shape[::-1])]

def reflect(shape):
    """좌우 대칭"""
    return [row[::-1] for row in shape]

def get_all_shapes(shape):
    shapes = []
    for _ in range(4):
        shape = rotate(shape)
        shapes.append(shape)
        shapes.append(reflect(shape))
    return shapes

def solution(n, m, grid):
    """
    세로 n, 가로 m 
    테트로미노가 놓인 칸에 쓰여 있는 수들의 최댓값 반환
    """  
    tet = [
        [[1, 1, 1, 1]], 
        [[1, 1], [1, 1]],
        [[1, 0], [1, 0], [1, 1]],
        [[1, 0], [1, 1], [0, 1]],
        [[1, 1, 1], [0, 1, 0]]
        ]
    
    answer = 0
    for te in tet:
        for t in get_all_shapes(te):
            w, h = len(t[0]), len(t)
            for i in range(m):
                if i + w > m:
                    break
                for j in range(n):
                    if j + h > n:
                        break
                    answer = max(
                        sum(sum(grid[l][k] for l in range(j, j+h, 1) if t[l-j][k-i]) for k in range(i, i+w, 1)), 
                        answer)
    return answer
        
if __name__ == "__main__":
    input = sys.stdin.readline
    N, M = tuple(map(int, input().split()))
    grid = [list(map(int, input().split())) for _ in range(N)]
    print(solution(N, M, grid))

python

이렇게 했는데 시간 초과가 나서 다른 방식으로 틀어서

계속 회전한 후에 대칭시켜도 되는 거면, 숫자칸(이하 grid)에서 붙어 있는 숫자 4개 조합을 dfs로 구해도 되지 않을까 생각했다. 그랬는데, ..

대각선의 관계를 갖는 도형도 있고 아닌 도형도 있어서 구현하기가 쉽지 않았다.

dfs 문제가 아님을 확인 후, 처음 코드로 돌아가서 chatgpt한테 시간 초과 나는 이유에 대해서 물어보니가 회전과 대칭을 만든 후에 중복 도형을 제거하는 코드를 추가하라는 답변을 받고

get_all_shapes() 함수에 중복 제거 코드를 추가하니 통과가 되었다..😱

def get_all_shapes(shape):
    shapes = []
    for _ in range(4):
        shape = rotate(shape)
        shapes.append(shape)
        shapes.append(reflect(shape))
    # 중복 제거
    unique = []
    for s in shapes:
        if s not in unique:
            unique.append(s)
    return unique

python

shape을 set으로 중복 제거하거나 딕셔너리로 중복 제거하는 것만 생각하고 list로 중복 제거할 생각은 시간이 오래 걸릴거라 생각해서 시도를 안 해봤다.

생각해보니 테트로미노의 회전/대칭으로 나올 수 있는 shape의 최대 개수는 8개에 불과. 따라서, 회전과 대칭을 모두 적용한 뒤 리스트에서 중복을 제거해도 연산량은 8번 비교에 불과

다음 문제부터는

데이터의 크기가 작으면 단순한 방법부터 시도해보기

최대 연산량을 직접 계산해보기

sol’s blog

백준 테트로미노

Tags