[python] 백준 14500 테트로미노

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

14500번: 테트로미노

 

문제 해결

사실 너무 어려웠다. 한 점을 잡고 이동을 해야할 것 같은데 어떻게 해야할 지 몰랐다.

이 모양을 제외 하면 모두 한 붓 그리기, 즉 다시 되돌아가지 않고 이동하면서 그릴 수 있다는 특징이 있다.

이 모형도 가운데를 중심으로 동,서,남,북 으로 이동 후 하나를 자른다는 생각을 할 수 있다. 자르는 것은 최소의 값을 가진 지역이라 할 수 있다.

 

행으로 +1+1+1 이동 혹은 -1 -1 -1 이동

이동하는 방법을 move = [ (1,0), (-1,0), (0, 1), (0, -1)] 로 한 다음 한 점을 잡고 for문과 dfs를 이용해서 3번 이동한다.

왔던 곳을 다시 되돌아 가면 안되기 때문에 visited = True/ False 를 이용해서 왔던 곳을 표시한다.

ㅗ,ㅏ,ㅜ,ㅓ 모양은 중심점을 잡고 동, 서, 남 북 점수를 합친 다음 4개중 최솟값을 뺀 값을 가져온다. 우리는 결국 행렬안에서 테트리스 모형 중 하나의 커널을 만들어 최댓값을 만드는 것이 목적이기 때문이다.

CODE

import sys
input = sys.stdin.readline
sys.setrecursionlimit(15000)
# 움직임
move = [(1,0), (0,1), (-1,0), (0,-1)]

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

maxValue = 0

def dfs(row, column, score, cnt): # 한 붓 그리기
    global maxValue
    if cnt == 4:
        maxValue = max(maxValue, score)
        return
    for i in range(4):
        new_row = row + move[i][0]
        new_column = column + move[i][1]
        if 0<= new_row < n and 0<= new_column < m and visited[new_row][new_column] == False:
            visited[new_row][new_column] = True
            dfs(new_row, new_column, score+board[new_row][new_column], cnt+1)
            visited[new_row][new_column] = False

# ㅏ ㅗ ㅜ ㅓ 모양
def fuck(row, column):
    global maxValue
    score = board[row][column]
    min_score = 1000
    x = 0
    for i in range(4):
        new_row = row + move[i][0]
        new_column = column + move[i][1]
        if 0<=new_row<n and 0<=new_column<m:
            score+= board[new_row][new_column]
            min_score = min(min_score, board[new_row][new_column])
        else:
            x += 1
            min_score =0
    if x >= 2: # 꼭짓점 지역은 ㅏ,ㅗ,ㅜ,ㅓ 모형을 만둘 수 없다.
        score = 0 # score 0으로 그냥 무시
    else:
        score -= min_score
    maxValue = max(maxValue, score)

for row in range(n):
    for column in range(m):
        visited[row][column] = True
        dfs(row,column,board[row][column], 1)
        visited[row][column] = False # 리셋
        fuck(row,column)
print(maxValue)