[Python | 14500] 테트로미노

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

---

문제 설명

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

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

 

📌 시간 제한: 2초

---

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

---

출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

---

문제 접근

문제는 4칸으로 이루어진 테트로미노 도형을 종이 위에 하나 올렸을 때, 해당 칸에 적힌 수의 합이 최대가 되도록 하는 값을 구하는 문제다. 입력으로는 N×M 크기의 2차원 배열이 주어지고, 테트로미노는 총 5가지 기본 도형을 회전, 대칭시켜 총 19가지 모양이 된다. 이 19가지 모양을 일일이 구현하는 것도 하나의 방법이지만, 효율성과 유지보수를 고려했을 때 DFS를 통해 만들 수 있는 모양은 재귀 탐색으로 처리하고, DFS로는 만들 수 없는 예외적인 모양만 따로 브루트포스로 처리하는 것이 훨씬 깔끔하다.

문제에서 요구하는 테트로미노는 모두 4칸으로 이루어져 있으므로, 각 좌표에서 시작해 4칸을 연결하는 경로를 만들면 대부분의 도형을 만들 수 있다. 이를 위해 DFS를 이용하여 각 칸을 시작점으로 4칸을 탐색하고, 이 경로의 합 중 가장 큰 값을 계속 갱신한다. DFS는 상하좌우 방향으로만 이동하며, 방문 여부를 체크해서 한 칸을 중복 방문하지 않도록 한다. 이렇게 하면 ㄱ자, ┘자, ─자, ㄴ자 등 대부분의 모양이 커버된다. 하지만 가운데를 중심으로 가지가 세 방향으로 뻗는 형태인 ㅗ, ㅜ, ㅏ, ㅓ 모양은 DFS로는 만들 수 없다. 이들 모양은 DFS처럼 한 방향으로 뻗어가는 방식으로는 구현이 불가능하기 때문에, 중심 좌표 기준으로 세 방향을 붙이는 방식으로 따로 처리해야 한다. 이 부분은 좌표를 직접 하드코딩하여 각각 브루트포스로 처리한다.

---

구현

코드에서 구현한 방식은 다음과 같다:

• DFS로 (x, y)에서 시작해 4칸까지 탐색하며 모든 경로의 합을 계산한다.
• 탐색 중에는 visited 배열을 사용해 중복 방문을 방지한다.
• DFS로 만들 수 없는 ㅗ 모양 계열은 (x, y)를 중심으로 세 방향을 붙이는 형태를 별도로 구현한다.
• 이때 try-except는 사용하지 않고, 직접 범위 검사를 통해 유효 좌표만 계산한다.

위와 같은 방식으로 구현하면, 회전/대칭 포함 19가지 도형을 모두 커버할 수 있으며, 불필요하게 모든 도형을 하드코딩할 필요 없이 구조적으로 처리할 수 있다. DFS의 깊이는 고정되어 있고(4칸), 매 칸에서 4방향만 탐색하므로 시간복잡도는 대략 O(N×M×4³)으로 계산할 수 있다. N, M이 최대 500이므로 최악의 경우에도 문제를 해결하는 데 무리가 없다.

결과적으로, DFS를 통해 탐색 가능한 모든 도형을 재귀로 처리하고, DFS로 만들 수 없는 도형만 하드코딩 방식의 브루트포스로 분리함으로써, 구현 난이도는 낮추고 효율성은 확보하는 구조로 문제를 해결할 수 있었다. DFS와 브루트포스를 적절히 나눠 사용하는 것이 포인트다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

# 방향 벡터: 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

max_sum = 0
visited = [[False] * m for _ in range(n)]

# DFS로 깊이 4까지 탐색 (테트로미노 모양 생성)
def dfs(x, y, depth, total):
    global max_sum

    # 4칸 완성되면 최대값 갱신
    if depth == 4:
        max_sum = max(max_sum, total)
        return
    
    # 상하좌우 인접한 곳으로 이동
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        # 범위 내 + 방문하지 않은 칸일 경우
        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
            visited[nx][ny] = True
            dfs(nx, ny, depth + 1, total + board[nx][ny])
            visited[nx][ny] = False

# ㅗ, ㅜ, ㅓ, ㅏ 모양은 DFS로 만들 수 없어서 별도 처리
def check_extra_shape(x, y):
    global max_sum
    center = board[x][y]
    
    # 중심을 기준으로 3개의 방향을 붙이는 방식
    shapes = [
        [(0, 1), (0, -1), (1, 0)],   # ㅗ
        [(0, 1), (0, -1), (-1, 0)],  # ㅜ
        [(1, 0), (-1, 0), (0, 1)],   # ㅏ
        [(1, 0), (-1, 0), (0, -1)]   # ㅓ
    ]

    # 각 모양 시도
    for shape in shapes:
        total = center
        valid = True
        for dx_, dy_ in shape:
            nx = x + dx_
            ny = y + dy_
            # 종이 범위 안에 있을 때만 합산
            if 0 <= nx < n and 0 <= ny < m:
                total += board[nx][ny]
            else:
                valid = False
                break
        if valid:
            max_sum = max(max_sum, total)

# 전체 칸에 대해 탐색 시작
for i in range(n):
    for j in range(m):
        # DFS 탐색
        visited[i][j] = True
        dfs(i, j, 1, board[i][j])
        visited[i][j] = False
        # 예외 모양 따로 처리
        check_extra_shape(i, j)

print(max_sum)