[백준 4920 / Python] 테트리스 게임

테트리스 게임

🔍 알고리즘 분류

• 구현
• 브루트포스

💡 문제 풀이

테트리스를 뒤집을 수 없고 회전만 가능함에 주의❗️

1. 가능한 테트리스 모양 모두 shapes에 저장
2. 격자판 모두 탐색하며 테트리스 모양 놓기
   • 테트리스 셀 중 하나라도 격자판 범위 벗어나면 pass
   • 격자판 범위 내라면 값 계산후 최댓값 갱신

📄 코드

• Python

import sys
input = sys.stdin.readline

shapes = [
    # 1
    [(0,0), (0,1), (0,2), (0,3)],
    [(0,0), (1,0), (2,0), (3,0)],

    # 2
    [(0,0), (0,1), (1,1), (1,2)],
    [(0,1), (1,0), (1,1), (2,0)],

    # 3
    [(0,1), (1,1), (2,0), (2,1)],
    [(0,0), (0,1), (0,2), (1,2)],
    [(0,0), (0,1), (1,0), (2,0)],
    [(0,0), (1,0), (1,1), (1,2)],

    # 4
    [(0,0), (0,1), (0,2), (1,1)],
    [(0,1), (1,0), (1,1), (2,1)],
    [(0,1), (1,0), (1,1), (1,2)],
    [(0,0), (1,0), (1,1), (2,0)]

    # 5
    [(0,0), (0,1), (1,0), (1,1)],
]

T = 1
while True:
    answer = -int(1e9)
    n = int(input())
    if n == 0:
        break
    arr = [list(map(int, input().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for s in shapes:
                total = 0
                for dx, dy in s: 
                    # 범위 벗어나면 해당 모양 pass
                    if not (0 <= i + dx < n and 0 <= j + dy < n):
                        break
                    total += arr[i + dx][j + dy]
                else:
                    answer = max(answer, total)

    print(f"{T}. {answer}")
    T += 1

• 시간복잡도: O(N^)