[백준/파이썬] 14500번: 테트로미노

문제

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

풀이

• 폴리오미노란 1×1 크기의 정사각형을 여러 개 붙인 도형
  • 정사각형은 서로 겹치면 안 된다.
  • 도형은 모두 연결되어 있어야 한다.
  • 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
• 테트로미노란 정사각형 4개를 이어 붙인 폴리오미노
• 다음과 같은 5가지가 있다.
  
• N×M인 종이 위에 테트로미노 하나를 놓아 칸에 쓰여 있는 수들의 합을 최대로 하여 출력
  • 회전이나 대칭을 시켜도 된다.

입력 받은 보드 위에서 블럭의 모양대로 탐색을 진행하는 함수를 각각 만들어 주어 문제를 해결했습니다.

1자 모양 블럭

def block1(graph):
    area = 0 # 넓이
    for i in range(n):
        for j in range(m-3):
            area = max(area, sum(graph[i][j:j+4]))
    return area

정사각형 블럭

def block2(graph):
    area = 0
    for i in range(n-1):
        for j in range(m-1):
            area = max(area, sum(graph[i][j:j+2]) + sum(graph[i+1][j:j+2]))
    return area

L자 모양 블럭

def block3(graph):
    n = len(graph)
    m = len(graph[0])
    area = 0
    for i in range(n-2):
        for j in range(m-1):
            area = max(area, graph[i][j] + graph[i+1][j] + graph[i+2][j] + graph[i+2][j+1])
    return area

지그재그 모양 블럭

def block4(graph):
    n = len(graph)
    m = len(graph[0])
    area = 0
    for i in range(n-2):
        for j in range(m-1):
            area = max(area, graph[i][j] + graph[i+1][j] + graph[i+1][j+1] + graph[i+2][j+1])
    return area

T자 모양 블럭

def block5(graph):
    n = len(graph)
    m = len(graph[0])
    area = 0
    for i in range(n-1):
        for j in range(m-2):
            area = max(area, sum(graph[i][j:j+3]) + graph[i+1][j+1])
    return area

각 모양의 합을 구하는 함수를 만들어 주었습니다.
그런데, 문제에서는 각 도형을 회전하거나 대칭형태로 만들어서도 최대합을 구할 수 있다고 명시되어 있습니다.

우선 회전이나 대칭을 시켜도 세로, 가로 2가지 모양만 존재하는 block1은 세로로 구하는 부분을 추가해주었습니다.

	# 가로 1자 모양
    for i in range(n-3):
        for j in range(m):
            area = max(area, graph[i][j] + graph[i+1][j] + graph[i+2][j] + graph[i+3][j])

정사각형 모양인 block2는 대칭, 회전을 시켜도 항상 그 모양을 유지하기 때문에 다른 방법을 더 취하진 않았습니다.

남은 3가지 블럭은 회전을 시킬 때마다 항상 모양이 변하게 됩니다.
이를 어떻게 해결하지 고민하다가 그냥 종이 자체를 돌려버리기로 결정했습니다.

다음과 같은 방식으로 리스트를 시계방향으로 90도 회전시킬 수 있습니다.

board = list(map(list, zip(*board[::-1])))

이 방법을 이용해 90도씩 3번 회전시켜 block3, block4, block5를 모두 다 실행시켜 주었습니다.

block5는 대칭을 시켜도 180도 회전한 방향과 일치하기 때문에 대칭했을 때를 고려하지 않아도 됩니다.
그러나 block3과 block4는 대칭을 했을 때 모양이 바뀌게 됩니다.
그러기 때문에 여기서 대칭된 모습을 함수 안에 포함시켜 계산하였습니다.

def block3(graph):
    n = len(graph)
    m = len(graph[0])
    area = 0
    for i in range(n-2):
        for j in range(m-1):
            area = max(area, graph[i][j] + graph[i+1][j] + graph[i+2][j] + graph[i+2][j+1], graph[i][j+1] + graph[i+1][j+1] + graph[i+2][j+1] + graph[i+2][j]) # 대칭 모양 추가
    return area

def block4(graph):
    n = len(graph)
    m = len(graph[0])
    area = 0
    for i in range(n-2):
        for j in range(m-1):
            area = max(area, graph[i][j] + graph[i+1][j] + graph[i+1][j+1] + graph[i+2][j+1], graph[i][j+1] + graph[i+1][j+1] + graph[i+1][j] + graph[i+2][j]) # 대칭 모양 추가
    return area

코드

import sys
input = sys.stdin.readline

def block1(graph):
    area = 0
    for i in range(n):
        for j in range(m-3):
            area = max(area, sum(graph[i][j:j+4]))
    
    for i in range(n-3):
        for j in range(m):
            area = max(area, graph[i][j] + graph[i+1][j] + graph[i+2][j] + graph[i+3][j])
    
    return area

def block2(graph):
    area = 0
    for i in range(n-1):
        for j in range(m-1):
            area = max(area, sum(graph[i][j:j+2]) + sum(graph[i+1][j:j+2]))
    return area

def block3(graph):
    n = len(graph)
    m = len(graph[0])
    area = 0
    for i in range(n-2):
        for j in range(m-1):
            area = max(area, graph[i][j] + graph[i+1][j] + graph[i+2][j] + graph[i+2][j+1], graph[i][j+1] + graph[i+1][j+1] + graph[i+2][j+1] + graph[i+2][j])
    return area

def block4(graph):
    n = len(graph)
    m = len(graph[0])
    area = 0
    for i in range(n-2):
        for j in range(m-1):
            area = max(area, graph[i][j] + graph[i+1][j] + graph[i+1][j+1] + graph[i+2][j+1], graph[i][j+1] + graph[i+1][j+1] + graph[i+1][j] + graph[i+2][j])
    return area

def block5(graph):
    n = len(graph)
    m = len(graph[0])
    area = 0
    for i in range(n-1):
        for j in range(m-2):
            area = max(area, sum(graph[i][j:j+3]) + graph[i+1][j+1])
    return area

if __name__ == "__main__":
    n,m = map(int,input().split())
    board = [list(map(int,input().split())) for _ in range(n)]
    answer = max(block1(board), block2(board), block3(board), block4(board), block5(board))

    for i in range(3):
        board = list(map(list, zip(*board[::-1])))
        answer = max(answer, block3(board), block4(board), block5(board))
    
    print(answer)