💻 백준 14500: 테트로미노

문제 소개 🧐

N×M 크기의 종이 위에 테트로미노(정사각형 4개를 이어 붙인 도형) 하나를 놓아, 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 만드는 문제. 테트로미노는 회전이나 대칭이 가능하다.

입력 📝

  • 첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어집니다. (4 ≤ N, M ≤ 500)
  • 둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어집니다. (1,000 이하의 자연수)

출력 📤

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

제한 ❌

  • 2초, 512MB

첫 번째 시도: DFS를 이용한 일반적인 테트로미노 탐색 👊

Idea

테트로미노는 4개의 정사각형으로 이루어져 있으므로, 각 칸에서 시작하여 깊이 우선 탐색(DFS)을 통해 4칸을 연결하는 모든 경우의 수를 탐색하고 합을 계산했다. 방문한 칸은 visited 배열로 관리하여 중복 방문을 피했다.

Code

import sys
from collections import deque

# 테트로미노 4칸, 그냥 4칸 이어져있기만 하면 되는듯?
# (i,j)  1.(0,4) 2.(3,1) 3.(3,1) 4.(2,3) 5.(2,2)

n, m = map(int, sys.stdin.readline().split())
d_pos = [(1,0), (0,1), (-1,0), (0,-1)]  # 하 우 상 좌

num_map = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
ans = 0

def get_max_num(x, y, depth, visited, sum_val):
    max_num = 0
    for dx, dy in d_pos:
        next_x = x + dx
        next_y = y + dy
        if (0 <= next_x < n) and (0 <= next_y < m) and not visited[next_x][next_y]:
            if depth < 4:
                visited[next_x][next_y] = True
                num = get_max_num(next_x, next_y, depth + 1, visited, sum_val + num_map[next_x][next_y])
                max_num = max(max_num, num)
            else:
                print(x, y, depth, sum_val)
                return sum_val
    return max_num

for i in range(n):
    for j in range(m):
        visited = [[False for _ in range(m)] for _ in range(n)]
        sum_val = num_map[i][j]
        print(i,j)
        max_num = get_max_num(i, j, 1, visited, sum_val)
        if ans < max_num:
            ans = max_num
print(ans)

Result

  • 실패! 😭
  • DFS만으로는 ‘ㅗ’ 모양의 테트로미노를 정확히 탐색하기 어렵다는 것을 깨달았다. 이 모양은 중앙에서 뻗어나가는 형태라 일반적인 DFS 경로로는 잡히지 않을 수 있다.

두 번째 시도: DFS와 ‘ㅗ’ 모양 별도 처리 ✨

Idea

일반적인 4칸 연결 테트로미노는 DFS로 탐색하고, ‘ㅗ’ 모양 테트로미노는 별도의 함수로 모든 가능한 위치에서 직접 확인하는 방식으로 접근했다. ‘ㅗ’ 모양은 4가지 회전/대칭 형태가 있으므로, 각 형태에 대해 시작점을 기준으로 4칸의 합을 계산했다.

Code

import sys

n, m = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]  # 하 상 좌 우

max_val = 0

# 4개 연결된 block 찾는 dfs
def dfs(r, c, depth, current_sum):
    global max_val
    # 4일때, max 값 찾기
    if depth == 4:
        max_val = max(max_val, current_sum)
        return

    # 블록 순회
    for i in range(4):
        nr, nc = r + dx[i], c + dy[i]
        if 0 <= nr < n and 0 <= nc < m and not visited[nr][nc]:
            visited[nr][nc] = True
            dfs(nr, nc, depth + 1, current_sum + board[nr][nc])
            visited[nr][nc] = False # 다음에 다시 돌아야하니깐, 다시 False로 바꿔주기

# 'ㅗ' 자 테트로미노 찾는 함수
def check_t_shape(r, c):
    global max_val
    
    t_shapes = [
        [(0, 0), (0, 1), (0, 2), (1, 1)],  # 기본 T shape
        [(0, 1), (1, 0), (1, 1), (1, 2)],  #  T shape
        [(0, 0), (1, 0), (2, 0), (1, 1)],  # Rotated T shape
        [(0, 1), (1, 1), (2, 1), (1, 0)]   # Rotated T shape
    ]

    for shape in t_shapes:
        temp_sum = 0
        is_valid = True
        for dr, dc in shape:
            nr, nc = r + dr, c + dc
            if not (0 <= nr < n and 0 <= nc < m):
                is_valid = False
                break
            temp_sum += board[nr][nc]
        
        if is_valid:
            max_val = max(max_val, temp_sum)

# 모든 노드 순회
for r in range(n):
    for c in range(m):
        # dfs 시작
        visited[r][c] = True
        dfs(r, c, 1, board[r][c])
        visited[r][c] = False
        
        # 'ㅗ'자 테트로미노에 대해서 따로 체크
        check_t_shape(r, c)

print(max_val)

Result

  • 성공! ✅
  • DFS로 탐색하기 어려운 특정 모양(여기서는 ‘ㅗ’ 모양)은 별도로 처리하는 것이 효과적이라는 것을 배웠다.

개선할 부분 🤔

  • ‘ㅗ’ 모양을 처리하는 check_t_shape 함수에서 하드코딩된 좌표 대신, 회전 및 대칭 변환을 일반화하는 방법을 고려해볼 수 있다. 하지만 N, M의 크기가 크지 않아 현재 방식도 충분히 효율적이다.