[백준 14500 : PYTHON] 테트로미노

문제 풀기 : 14500번

14500번: 테트로미노

 

문제

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

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

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

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 수를 구하라.

테트로미노는 회전이나 대칭을 시켜도 된다.

 

문제풀이

보드위에 테트로미노 하나를 놓아서 가장 최대가 되는 수를 찾는 문제이다. (처음엔 여러 개 놓는 문제인 줄 알았다...)

5개의 테트로미노를 어떻게 놓을지 고민해보자.

테트로미노를 자세히보면 4개의 정사각형으로 이루어져 있고 4개의 테트로미노는 연달아 이을 수 있지만 1개는 그렇지 않다. 그림을 보자!

왼쪽에 있는 테트로미노는 dfs로 상하좌우 최대 4번까지 돌려서 모양을 얻을 수 있지만, 오른쪽에 있는 테트로미노는 경우를 다르게 해주어야 한다는 것을 알 수 있을 것이다. 이해가 안 된다면 다음 설명을 보면된다.

왼쪽을 먼저 살펴보자!

회전과 대치를 시킨 모양들이다. 이 모양들은 상하좌우로 단 4번의 움직임으로 나올 수 있는 모든 모양이다. 신기했다.

진짜 그럴까 하신 분들은 아래의 표에서 아무렇게나 4번 움직여서 확인하시면 됩니다.

그럼 이제 오른쪽에 있는 모양의 경우의 수를 따져보자면 이렇다.

이 경우엔 가운데를 중심으로 3개의 날개(?)를 고려하면된다. 위에선 상하좌우 4가지 방향을 고려했지만 여기선 dfs를 돌릴 필요도 없고 4가지 경우를 순차적으로 확인하면 된다.

코드에서 중요한 부분을 몇 가지 언급하자면,

dfs를 돌릴 땐 중복 방문을 피하기 위해 visited를 만들어 방문여부를 꼭 확인하고 dfs가 끝나면 방문했던 곳은 방문해제를 해준다.

ㅗ 모양의 날개(?)부분을 확인할 때 방향 한 개만 뺀 경우를 따질 때는 좌표를 미리 적어두어 사용해도 되지만 나의 경우엔 상하좌우(move) 배열을 그대로 사용했다.  t = (n+k)%4 계산식을 사용해서 3개의 인덱스만을 탐색했다.

 

전체코드

import sys
input = sys.stdin.readline

# 상, 하, 좌, 우
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# INPUT
N, M = map(int, input().split())
board = [list(map(int,input().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]

# 최대값 변수
maxValue = 0

# ㅗ, ㅜ, ㅓ, ㅏ 제외한 모양들 최대값 계산
def dfs(i, j, dsum, cnt):
    global maxValue
    # 모양 완성되었을 때 최대값 계산
    if cnt == 4:
        maxValue = max(maxValue, dsum)
        return

    # 상, 하, 좌, 우로 이동
    for n in range(4):
        ni = i+move[n][0]
        nj = j+move[n][1]
        if 0 <= ni < N and 0 <= nj < M and not visited[ni][nj]:
            # 방문 표시 및 제거
            visited[ni][nj] = True
            dfs(ni, nj, dsum + board[ni][nj], cnt+1)
            visited[ni][nj] = False


# ㅗ, ㅜ, ㅓ, ㅏ 모양의 최대값 계산
def exce(i, j):
    global maxValue
    for n in range(4):
        # 초기값은 시작지점의 값으로 지정
        tmp = board[i][j]
        for k in range(3):
            # move 배열의 요소를 3개씩 사용할 수 있도록 인덱스 계산
            # 012, 123, 230, 301
            t = (n+k)%4
            ni = i+move[t][0]
            nj = j+move[t][1]

            if not (0 <= ni < N and 0 <= nj < M):
                tmp = 0
                break
            tmp += board[ni][nj]
        # 최대값 계산
        maxValue = max(maxValue, tmp)


for i in range(N):
    for j in range(M):
        # 시작점 visited 표시
        visited[i][j] = True
        dfs(i, j, board[i][j], 1)
        visited[i][j] = False

        exce(i, j)

print(maxValue)