백준 14500: 테트로미노(python)

문제

---

풀이

 

dfs로 풀이할 수도 있다던데, 그냥 브루트포스로 풀었다.

다섯 종류의 테트로미노를 회전 및 대칭하여 만들 수 있는 모양은 위의 열아홉가지이며, 이들 전부를 배열에 미리 세팅해 놓고 for문 순회하며 모든 경우를 탐색한다.

moves = [   # (dx, dy)
    # ㅡ
    [(0, 0), (0, 1), (0, 2), (0, 3)],
    [(0, 0), (1, 0), (2, 0), (3, 0)],
    # ㅁ
    [(0, 0), (0, 1), (1, 0), (1, 1)],
    # L
    [(0, 0), (-1, 0), (-1, -1), (-1, -2)],# 1
    [(0, 0), (1, 0), (1, -1), (1, -2)],   # 2
    [(0, 0), (0, 1), (-1, 1), (-2, 1)],   # 3
    [(0, 0), (0, 1), (1, 1), (2, 1)],     # 4
    [(0, 0), (0, -1), (1, -1), (2, -1)],  # 5
    [(0, 0), (0, -1), (-1, -1), (-2, -1)],# 6
    [(0, 0), (-1, 0), (-1, 1), (-1, 2)],  # 7
    [(0, 0), (1, 0), (1, 1), (1, 2)],     # 8
    # Z
    [(0, 0), (0, 1), (1, 1), (1, 2)],   # 1
    [(0, 0), (0, 1), (-1, 1), (-1, 2)], # 2
    [(0, 0), (-1, 0), (-1, 1), (-2, 1)],# 3
    [(0, 0), (1, 0), (1, 1), (2, 1)],   # 4
    # ㅗ
    [(0, 0), (1, 0), (2, 0), (1, 1)],   # 1
    [(0, 0), (0, -1), (0, -2), (1, -1)],# 2
    [(0, 0), (0, 1), (0, 2), (-1, 1)],  # 3
    [(0, 0), (1, 0), (2, 0), (1, -1)]   # 4
]

가독성을 위해 테트로미노 모양별로 정리하였으며 주석에 표시된 인덱스는 그림의 번호이다.

이때 한 점을 기준으로 회전, 대칭한다 생각하고 모든 이동이 기준점(그림의 X자)에서 시작하도록 설정해야 하는데, 기준점은 다르게 설정해도 상관 없지만 테트로미노별로 기준점이 다른 회전. 대칭이 하나라도 있으면 틀리므로 신경써줘야 한다.

maxSum = 0

for i in range(N):
    for j in range(M):  # x
        for k in range(19):
            currSum = 0
            isValid = True
            for dx, dy in moves[k]:
                x, y = j + dx, i + dy
                if 0 <= x < M and 0 <= y < N:
                    currSum += arr[y][x]
                else:
                    isValid = False
                    break
            if isValid and currSum > maxSum:
                maxSum = currSum

이후는 그냥 모든 칸에 대해 moves 전체를 탐색하며 최댓값을 찾으면 된다.

 

전체 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())    # 세로 N, 가로 M
arr = [list(map(int, input().split())) for _ in range(N)]

moves = [   # (dx, dy)
    # ㅡ
    [(0, 0), (0, 1), (0, 2), (0, 3)],
    [(0, 0), (1, 0), (2, 0), (3, 0)],
    # ㅁ
    [(0, 0), (0, 1), (1, 0), (1, 1)],
    # L
    [(0, 0), (-1, 0), (-1, -1), (-1, -2)],# 1
    [(0, 0), (1, 0), (1, -1), (1, -2)],   # 2
    [(0, 0), (0, 1), (-1, 1), (-2, 1)],   # 3
    [(0, 0), (0, 1), (1, 1), (2, 1)],     # 4
    [(0, 0), (0, -1), (1, -1), (2, -1)],  # 5
    [(0, 0), (0, -1), (-1, -1), (-2, -1)],# 6
    [(0, 0), (-1, 0), (-1, 1), (-1, 2)],  # 7
    [(0, 0), (1, 0), (1, 1), (1, 2)],     # 8
    # Z
    [(0, 0), (0, 1), (1, 1), (1, 2)],   # 1
    [(0, 0), (0, 1), (-1, 1), (-1, 2)], # 2
    [(0, 0), (-1, 0), (-1, 1), (-2, 1)],# 3
    [(0, 0), (1, 0), (1, 1), (2, 1)],   # 4
    # ㅗ
    [(0, 0), (1, 0), (2, 0), (1, 1)],   # 1
    [(0, 0), (0, -1), (0, -2), (1, -1)],# 2
    [(0, 0), (0, 1), (0, 2), (-1, 1)],  # 3
    [(0, 0), (1, 0), (2, 0), (1, -1)]   # 4
]

maxSum = 0

for i in range(N):
    for j in range(M):  # x
        for k in range(19):
            currSum = 0
            isValid = True
            for dx, dy in moves[k]:
                x, y = j + dx, i + dy
                if 0 <= x < M and 0 <= y < N:
                    currSum += arr[y][x]
                else:
                    isValid = False
                    break
            if isValid and currSum > maxSum:
                maxSum = currSum

print(maxSum)

시간이 그리 오래 걸리지는 않는 듯