[Python] BOJ / 14500번 / 테트로미노

14500번: 테트로미노

 

📝 문제

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

정사각형은 서로 겹치면 안 된다.
도형은 모두 연결되어 있어야 한다.
정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

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

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

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

 

📜 풀이

• 배열의 한 위치에서 깊이가 3인 DFS를 수행하면, 문제에 제시된 5가지의 테트로미노 중 'ㅗ' 모양을 제외한 나머지 모양과 같은 경로로 탐색을 수행할 수 있음
  • 해당 모양에 대한 회전 및 대칭 모양에 대해서도 마찬가지
• 즉, DFS를 수행하면서 해당 칸에 쓰여 있는 수들을 더해가다가 깊이가 3이되는 시점에, 최댓값을 갱신하는 식으로 구현하면 'ㅗ' 모양을 제외한 나머지 모양에 대한 최댓값을 찾을 수 있음
• 'ㅗ' 모양의 경우 현재 위치를 기준으로 상하좌우에 있는 네 가지 칸 중에서 세 가지 칸만 골라 더하는 모든 경우의 수를 고려하여 최댓값을 갱신하는 식으로 구현할 수 있음
  • 이는 편의상 조합(combination)을 사용하였음

 

💻 소스코드

from itertools import combinations
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

mv = [(0, 1), (1, 0), (0, -1), (-1, 0)]

# dfs(y축 위치, x축 위치, 깊이, 칸에 쓰여있는 값의 합)
def dfs(y, x, cnt, sum):
    global ans

    # 정사각형 4개를 모두 이어붙인 경우
    if cnt == 3:
        ans = max(ans, sum) # 최댓값 갱신
        return
    
    for dy, dx in mv:
        ny = y + dy
        nx = x + dx

        if 0 <= ny < n and 0 <= nx < m and not visited[ny][nx]:
            visited[ny][nx] = 1
            dfs(ny, nx, cnt + 1, sum + graph[ny][nx])
            visited[ny][nx] = 0

# 'ㅗ' 모양 테트로미노 계산
def sub(y, x):
    global ans

    # 현재 위치에서 상하좌우에 있는 4가지 칸 중 3가지만 고르는 경우를 모두 고려
    for coms in combinations(mv, 3):
        sum = graph[y][x]   # 중앙값

        for dy, dx in coms:
            ny = y + dy
            nx = x + dx

            # 한 칸이라도 종이 밖으로 빠져나온다면 해당 모양대로는 놓을 수 없음
            if not (0 <= ny < n and 0 <= nx < m):
                break
            
            sum += graph[ny][nx]
        
        # 최댓값 갱신
        ans = max(ans, sum)

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
ans = 0

# 모든 시작 위치에 대하여 DFS를 수행
for i in range(n):
    for j in range(m):
        visited[i][j] = 1
        dfs(i, j, 0, graph[i][j])
        visited[i][j] = 0

        sub(i, j)

print(ans)